New Parallel Prefix Algorithms


Lin Y., Hung L.

9th WSEAS International Conference on Applied Informatics and Communications, Moscow, Rusya, 20 - 22 Ağustos 2009, ss.204-207 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Basıldığı Şehir: Moscow
  • Basıldığı Ülke: Rusya
  • Sayfa Sayıları: ss.204-207
  • İstanbul Teknik Üniversitesi Adresli: Hayır

Özet

New families of computation-efficient parallel prefix algorithms for message-passing multicomputers are presented. The first family improves the communication time of a previous family of parallel prefix algorithms; both use only half-duplex communications. Two other families adopt collective communication operations to reduce the communication times of the former two, respectively. These families each provide the flexibility of either fewer computation time steps or fewer communication time steps to achieve the minimal running time depending on the ratio of the time required by a communication step to the time required by a computation step.