Modeling parallel computation using Work-Depth models

There are many different ways to organize the parallel computers, hence to model them also. An alternative way is to focus on algorithm. One approach is work-depth where cost of an algorithm is determined by examining the total number of operations that it performs and the dependencies among those operations. An algorithm's work $W$ is the total number of operations that it performs; and its depth $D$ is the longest chain of dependencies among its operations. The ratio $P = W/D$ is parallelism of the algorithm. A parallel algorithm is work efficient as compared to a sequential algorithm.

The work-depth models are more abstract than the multi-processor models. The algorithms that are efficient in the work-depth (w-d) models can be translated to algorithms that efficient in the multiprocessor models, and from these models they can be translated to parallel computers. The advantage of w-d models are that they do not have machine dependent details, which otherwise would complicate the design and their analysis.

There are three types of w-d models: circuit models, vector machine models, language-based models.