loading...
Efficient Two-Level Mesh based Simulation of PRAMs
Beijing, CHINA June 12-June 14
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ISPAN.1996.5089571996 International Symposium on Paral ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Martti Forsell, Department of Computer Science University of Joensuu, Finland
Martti Penttonen, Department of Computer Science University of Joensuu, Finland
Ville Leppänen, Department of Computer Science University of Turku, Finland
We consider time-processor optimal simulations of PRAM models on coated block meshes. A coated block mesh consists of \pi-processor blocks and \pi \times \pi or \sqrt{\pi} \times \sqrt{\pi} \times \sqrt{\pi} router blocks. The router blocks form a 2-dimensional or a 3-dimensional regular mesh, and the processor & memory blocks are located on the surface of the block mesh. As a generalization of the coated mesh, the 2-dimensional and 3-dimensional coated block meshes simulate EREW, CREW, and CRCW PRAM models time-processor optimally with moderate simulation cost. Using proper amount of parallel slackness, the cost can be decreased clearly below 2 routing steps per simulated PRAM processor.The coated block mesh is actually an instance of a more general two-level construction technique, which uses a seemingly inefficient but scalable solution on top of a non-scalable but efficient solution. Within blocks (chips) brute force techniques are applied, whereas the mesh structure on top makes the whole construction modular, simple, and scalable. The parameter \pi provides a method to balance the construction with respect to the two techniques.
Index Terms:
PRAM, shared memory machine, simulation, time-processor optimal, mesh, interconnection network
Citation:
Martti Forsell, Martti Penttonen, Ville Leppänen, "Efficient Two-Level Mesh based Simulation of PRAMs," ispan, pp.29, 1996 International Symposium on Parallel Architectures, Algorithms and Networks (ISPAN '96), 1996
Usage of this product signifies your acceptance of the Terms of Use.


Suggestions