When we talk about a best-case scenario, are we talking about best-case scenarios when the hardware is optimal? When the algorithm is optimal? When the actual input running the algorithm is optimal?
Updog
Best-case scenario would be the fastest the hardware could possibly run the program. For instance how many math ops/sec can the CPU do. Or what is the maximum memory bandwidth. For instance the SAXPY program from assignment 1 is memory bandwidth limited, so achieving the maximum bandwidth of the machine is the best-case scenario. I actually tried just now, and sure enough if you remove all the math from SAXPY and just do 2 loads and a store, you still get the same throughput.
randomthread
I think we are optimizing for the given hardware on the basis of an application dependent performance metric. Thus a non-optimal algorithm from a complexity perspective might give better performance if its mapping to the hardware gives better utilization than more optimal algorithms. The performance should be evaluated over the distribution of the inputs to give an unbiased evaluation.
When we talk about a best-case scenario, are we talking about best-case scenarios when the hardware is optimal? When the algorithm is optimal? When the actual input running the algorithm is optimal?
Best-case scenario would be the fastest the hardware could possibly run the program. For instance how many math ops/sec can the CPU do. Or what is the maximum memory bandwidth. For instance the SAXPY program from assignment 1 is memory bandwidth limited, so achieving the maximum bandwidth of the machine is the best-case scenario. I actually tried just now, and sure enough if you remove all the math from SAXPY and just do 2 loads and a store, you still get the same throughput.
I think we are optimizing for the given hardware on the basis of an application dependent performance metric. Thus a non-optimal algorithm from a complexity perspective might give better performance if its mapping to the hardware gives better utilization than more optimal algorithms. The performance should be evaluated over the distribution of the inputs to give an unbiased evaluation.