并行计算是指同时使用多个计算机处理器 (CPU) 而不是仅使用一个处理器来执行计算机程序。令 
为最快的已知串行算法的运行时间，令 
为在 
个处理器上执行的并行算法的运行时间，其中 
是输入的大小。
加速比定义为
 |
即，串行执行时间与并行执行时间的比率。理想情况下，人们希望 
，这被称为完美加速比，尽管在实践中很少实现。（在某些情况下，由于内存层次结构效应，可以实现超线性加速比。）
衡量并行算法性能的另一个指标是效率，
，定义为
 |
人们可以使用加速比和效率来分析算法，可以从理论上使用渐近运行时复杂度，也可以在实践中通过测量程序执行时间。当 
固定时，加速比和效率是等效的度量，仅相差常数因子 
。
