imported>David Eppstein: Eunice Santos

2023-07-11T22:31:21Z

New page

The '''LogP machine''' is a model for [[parallel computation]].<ref>Culler et al. 1993</ref>
It aims at being more practical than the [[Parallel random-access machine |PRAM]] model while still allowing for easy analysis of computation.
The name is not related to the [[Logarithm|mathematical logarithmic function]]: Instead, the machine is described by the four parameters <math>L</math>, <math>o</math>, <math>g</math> and <math>P</math>.

The LogP machine consists of arbitrarily many processing units with [[distributed memory]].
The processing units are connected through an abstract communication medium which allows point-to-point communication. This model is pair-wise synchronous and overall asynchronous.

The machine is described by the four parameters:

* <math>L</math>, the [[Latency (engineering)|latency]] of the communication medium.
* <math>o</math>, the [[Overhead (computing)|overhead]] of sending and receiving a message.
* <math>g</math>, the gap required between two send/receive operations. A more common interpretation of this quantity is as the inverse of the [[Bandwidth (computing)|bandwidth]] of a processor-processor communication channel.
* <math>P</math>, the number of processing units.

Each local operation on each machine takes the same time ('unit time'). This time is called a processor cycle. The units of the parameters <math>L</math>, <math>o</math> and <math>g</math> are measured in multiples of processor cycles.

== See also ==

* [[Bulk synchronous parallel]]
* [[Parallel programming model]]

== Notes ==
{{reflist|2}}

== References ==

{{Citation
| last = Culler
| first = David
| title = LogP: Towards a realistic model of parallel computation
| journal = ACM SIGPLAN Notices
| volume = 28
| issue = 7
| pages = 1–12
| date = July 1993
| url = https://dl.acm.org/doi/pdf/10.1145/173284.155333
| doi = 10.1145/173284.155333
| last2 = Karp
| first2 = Richard
| last3 = Patterson
| first3 = David
| last4 = Sahay
| first4 = Abhijit
| last5 = Schauser
| first5 = Klaus Erik
| last6 = Santos
| first6 = Eunice | author6-link=Eunice Santos
| last7 = Subramonian
| first7 = Ramesh
| last8 = Von Eicken
| first8 = Thorsten| citeseerx = 10.1.1.319.7827
}}

[[Category:Educational abstract machines]]
[[Category:Theoretical computer science]]
[[Category:Models of computation]]
[[Category:Parallel computing]]

{{Comp-sci-stub}}

LogP machine - Revision history

imported>David Eppstein: Eunice Santos