A "frame" is once around the game loop:
while( game_running ): update() draw() update() involves things like
- Reading user input
- Computing enemy next moves
draw() is just drawing the current state of the game, as computed by update().
So here a "frame" is BOTH an update/draw cycle. FPS (frames per second) is a rough measure of how many times you can do your basic game loop per second, so by that its a rough measure of game performance.
Any number of things can be the bottle neck in your frame rate. It could be the CPU intensive AI code. It could be your collision detection routines before you added a reasonable space partitioning scheme. It could be the GPU itself.
If it contains an accurate physics solver, your physics solver will need to perform more than one iteration step per "frame" displayed (CarSim for example requires something like 1000 iterations every 1/60 second, simply to retain stability in the solution).