Efficient PRAM simulations

• Choose a simple hash function.
  
• Hash PRAM's shared memory to local memory modules
  
• Setup a virtual "coated" DAG (logical diameter D; routing capacity Omega (PD))
  
• Allocate Omega(D) threads (virtual PRAM processors) to each real processor.
  
• Route memory requests greedily.
  
• Keep consecutive PRAM steps separate with a syncronization wave.
  

• What coated DEG? Mesh? Mesh of trees? Fat tree? Butterfly?
  
• How to implement the DAG?
  
• Where to get the threads? A: Plenty of work-optimal NC-algorithms exists.
  
  

Research Team of our Parallel Computing project

• (Head) Professor Martti Penttonen (University of Joensuu/Computer Science)
  
• Martti Forsell (University of Joensuu/Computer Science)
  
• Simo Juvaste (University of Joensuu/Computer Science)
  
• Anssi Kautonen (University of Joensuu/Computer Science)
  
• Ville Leppänen (University of Turku/Computer Science)
  

Last updated, Feb-5-1996.