Loading...
Please wait, while we are loading the content...
Similar Documents
Communication-processor tradeoffs in limited resources pram.
| Content Provider | CiteSeerX |
|---|---|
| Author | Agbaria, Adnan Ben-Asher, Yosi Newman, Ilan |
| Abstract | We consider a simple restriction of the PRAM model (called PPRAM), where the input is arbitrarily partitioned between a fixed set of p processors and the shared memory is restricted to m cells. This model allows for investigating the tradeoffs/ bottlenecks with respect to the communication bandwidth (modeled by the shared memory size m) and the number of processors p. The model is quite simple and allows the design of optimal algorithms without loosing the effect of communication bottlenecks. We have focused on the PPRAM complexity of problems that have O(n) sequential solutions (where n is the input size), and where m p n. We show tight time bounds for several problems in this model such as summing, Boolean threshold, routing, integer sorting, list reversal and k-selection. We get typically two sorts of complexity behaviors for these problems: Either ~ O(n=p+p=m) which means that the time scales with the number of processors and with memory size (in appropriate range) but... |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Communication-processor Tradeoff Limited Resource Pram Appropriate Range Complexity Behavior Optimal Algorithm Fixed Set Shared Memory Communication Bandwidth Simple Restriction Memory Size Integer Sorting Boolean Threshold Tight Time Bound Several Problem Shared Memory Size List Reversal Communication Bottleneck Input Size Pram Model Tradeoff Bottleneck Ppram Complexity Sequential Solution |
| Content Type | Text |
