論文

査読有り
2009年1月

The Third Homomorphism Theorem on Trees Downward & Upward Lead to Divide-and-Conquer

ACM SIGPLAN NOTICES
  • Akimasa Morihata
  • ,
  • Kiminori Matsuzaki
  • ,
  • Zhenjiang Hu
  • ,
  • Masato Takeichi

44
1
開始ページ
177
終了ページ
185
記述言語
英語
掲載種別
研究論文(学術雑誌)
出版者・発行元
ASSOC COMPUTING MACHINERY

Parallel programs on lists have been intensively studied. It is well known that associativity provides a good characterization for divide-and-conquer parallel programs. In particular, the third homomorphism theorem is not only useful for systematic development of parallel programs on lists, but it is also suitable for automatic parallelization. The theorem states that if two sequential programs iterate the same list leftward and rightward, respectively, and compute the same value, then there exists a divide-and-conquer parallel program that computes the same value as the sequential programs.
While there have been many studies on lists, few have been done for characterizing and developing of parallel programs on trees. Naive divide-and-conquer programs, which divide a tree at the root and compute independent subtrees in parallel, take time that is proportional to the height of the input tree and have poor scalability with respect to the number of processors when the input tree is ill-balanced.
In this paper, we develop a method for systematically constructing scalable divide-and-conquer parallel programs on trees, in which two sequential programs lead to a scalable divide-and-conquer parallel program. We focus on paths instead of trees so as to utilize rich results on lists and demonstrate that associativity provides good characterization for scalable divide-and-conquer parallel programs on trees. Moreover, we generalize the third homomorphism theorem from lists to trees. We demonstrate the effectiveness of our method with various examples. Our results, being generalizations of known results for lists, are generic in the sense that they work well for all polynomial data structures.

Web of Science ® 被引用回数 : 22

リンク情報
DBLP
https://dblp.uni-trier.de/rec/conf/popl/MorihataMHT09
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000272013800017&DestApp=WOS_CPL
URL
http://doi.acm.org/10.1145/1480881.1480905
URL
http://dblp.uni-trier.de/db/conf/popl/popl2009.html#conf/popl/MorihataMHT09
ID情報
  • ISSN : 0362-1340
  • DBLP ID : conf/popl/MorihataMHT09
  • Web of Science ID : WOS:000272013800017

エクスポート
BibTeX RIS