3 ms·
This Parallel & Sequential Algorithms book from CMU uses a simpler language cost model instead of the traditional machine based model to do analysis if anybody
by hackermailman 8y ago
This Parallel & Sequential Algorithms book from CMU uses a simpler language cost model instead of the traditional machine based model to do analysis if anybody is interested
http://www.parallel-algorithms-book.com/ http://www.parallel-algorithms-book.com/
When using a machine model, we have to reason about how the algorithm compiles and runs on that machine. For example, if we express our algorithm in a low-level language such as C, cost analysis based on a machine model that represents a von Neumanm machine is straightforward because there is an almost one-to-one mapping of statements in C to the instructions of such a machine. For higher-level languages, this becomes trickier. There may be uncertainties, for example, about the cost of automatic memory management, or the cost of dispatching in an object-oriented language. For parallel programs, cost analysis based on machine-based models even more tricky, since we have to reason about how parallel tasks of the algorithm are scheduled on the processors of the machine.