Next: Designing Parallel Algorithms Up: Modeling parallel computation using Previous: Vector Model
In a language model, a work-depth cost is associated with each programming language construct. For example, work of calling two functions in parallel is equal to sum of the work of two calls. The depth is equal to the maximum of the depth of the two calls.
Assigning cost to algorithms. In the work-depth models, the cost of an algorithm is determined by its work and by its depth. The notions of work and depth can also be defined for the multiprocessor models. The work 
performed by an algorithm is equal to the number of processors multiplied by the time required for the algorithm to complete execution. The depth 
is equal to the total time required to execute the algorithm.
The depth of an algorithm is important, because there are some applications for which the time to perform a computation is crucial. For example, the results of a weather forecasting program are useful only if the program completes execution before the weather does!
Generally, however, the most important measure of the cost of an algorithm is the work. This can be argued as follows. The cost of a computer is roughly proportional to the number of processors in the computer. The cost for purchasing time on a computer is proportional to the cost of the computer multiplied by the amount of time used. The total cost of performing a computation, therefore, is roughly proportional to the number of processors in the computer multiplied by the amount of time, i.e., the work.
In many instances, the cost of running a computation on a parallel computer may be slightly larger than the cost of running the same computation on a sequential computer. If the time to completion is sufficiently improved, however, this extra cost can often be justified. As we shall see, however, there is often a trade-off between time-to-completion and total work performed. To quantify when parallel algorithms are efficient in terms of cost, we say that a parallel algorithm is work-efficient if asymptotically (as the problem size grows) it requires at most a constant factor more work than the best sequential algorithm known.