Loading...
Please wait, while we are loading the content...
Similar Documents
Sparse computations and Multi-BSP
| Content Provider | Semantic Scholar |
|---|---|
| Author | Yzelman, A. N. |
| Copyright Year | 2016 |
| Abstract | BSP is a simple but effective model for parallel computing. A BSP computer (p, g, l) consists of p sequential processors with sufficient local memory. A black-box network interconnects these. This network is assumed to be full duplex and optimised for all-to-all communication; a processor can thus simultaneously send and receive a single data word at constant cost g. The network has an associated latency cost l that has a more complete interpretation in the following context. A BSP algorithm (p, wi,s, hi) consists of a series of supersteps. It is described as a sequential program parametrised in p as well as in the process ID s ∈ {0, 1, . . . , p − 1}. A superstep consists of computation and communication. Computation is a set of operations on local data using only local processor resources. Communication is a global action that involves only the network and is disallowed from affecting computation that occur in the same superstep, and vice versa. Computation at the ith superstep of process s may assume that all communication in preceding supersteps, as far as they affect the state of memory local to process s, have completed. A program needs the network to determine whether it is safe to advance a superstep; this is exactly the latency cost l introduced earlier. The sequential work in the ith superstep at process s has cost wi,s. The number of data words sent and received by process s as part of the ith superstep are ti,s and ri,s, respectively. The h-relation of the ith superstep, the cost of the process that forms the communication bottleneck, is hi = maxs max{ti,s, ri,s}: the cost incurred by the process which has to send or receive the largest number of data words of all processes during superstep i. Given a BSP computer (p, g, l) and a BSP algorithm (p, wi,s, hi), the cost of running that algorithm on that computer is |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.eecs.wsu.edu/~assefaw/CSC16/slides/albert_yzelman_CSC16.pdf |
| Alternate Webpage(s) | http://www.eecs.wsu.edu/~assefaw/CSC16/abstracts/yzelman-CSC16_paper_15.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
