The exam can only be done by approved panel physicians. There is a list of them on the CIC website here : http://www.cic.gc.ca/pp-md/pp-list.aspx
Yes you can do the exam before submitting your application. When you do the exam, you need to tell the doctor which immigration stream your are applying through so he knows what to do. The doctor will send in the results electronically to CIC and will give you a report to submit with your application, as proof that you have done the medicals. Make a copy for yourself.
The medical exams are valid for 1 year only. If they expire while your application is still in process, CIC might extend them, or ask you to do them again.