Parallel Communication Mechanisms for Sparse, Irregular Appl

Parallel Communication Mechanisms for Sparse,Irregular Applications

Frederic T.Chong

1

2

Abstract

Parallel systems are becoming a signi?cant computing technology,not only for high performance computing,but also for commodity servers.The goal of this research is to identify core communica-tion mechanisms which both exploit architectural trends and support real applications.We demonstrate that cache-coherent shared memory hardware is such a core mechanism,even for applications with lit-tle data re-use and data-driven synchronization.This thesis makes three major contributions.First,we perform an in-depth study of the interaction between communication mechanisms and sparse,irregu-lar applications.Second,we present the Remote Queues(RQ)communication model,an abstraction which synthesizes more ef?cient synchronization for hardware-supported shared memory and other complex systems.Third,we characterize the relative performance of all of our mechanisms as proces-sor speed and machine size scale.

On the MIT Alewife Multiprocessor,we?nd that shared memory provides high performance with lower code complexity than message passing on our irregular problems.This is primarily due to four reasons.First,a5-to-1ratio between global and local cache misses makes memory copies in bulk communication expensive relative to communication via shared memory.Second,although message passing has synchronization semantics superior to shared memory for data-driven computation,ef?-cient shared memory can overcome this handicap by using global read-modify-writes to change from the traditional owner-computes model to a producer-computes model.Third,the Remote Queues communication model generalizes such a change,providing the semantics and performance of polling active messages on a wide variety of systems.Fourth,bulk transfers can result in high processor idle times in irregular applications.

Finally,we characterize multiprocessor design points where message passing and bulk transfer can perform better than shared memory.In particular,we?nd that shared memory uses more than four times the network bandwidth as message passing.Unless an application’s performance is already limited by local memory speeds,network bandwidth and latency threaten to become a serious problem. Our study indicates that machines based on modern microprocessors,such as the Cray T3E,must resort to expensive,high-dimensional networks to support shared-memory traf?c.Furthermore,the round-trip nature of shared memory may not be able to tolerate the latencies of future networks.

3

4

Acknowledgments

I would like to thank Anant Agarwal for some great advising over the years.He helped steer me through a rewarding graduate career.His enthusiasm and energy is amazing.Whenever I felt a little burned-out,a short meeting with Anant would have me charging for a couple more weeks.

I would also like to thank the rest of my committee.I have enjoyed my interactions with Tom Leighton since my work on interconnection networks for my Master’s thesis.A ten-minute talk with Tom can solve problems that might otherwise take months.An early meeting with Joel Saltz at Thinking Machines got me started on irregular applications.His perspective and extensive research group have helped me immensely.Rob Schreiber hosted my stay at NASA and helped me delve into what I saw as numerical voodoo.He taught me to look at sparse matrix computations as graph computations that I could understand more intuitively.

I would also like to thank Tom Knight for advising my master’s thesis and helping my growth from back when I was an undergraduate.I had a lot of good times in his group.

I would like to thank Eric Brewer for being a great friend,colleague,and example.I miss the times when we were just a couple?oors apart.I think he was the peer that I learned the most from.

My graduate career has been largely a product of the environment here at the lab.For that I have the members of the Alewife group to thank,especially John Kubiatowicz,whose unparalleled knowledge and service form the heart of the group.Thanks to Kirk Johnson, David Chaiken,Ken Mackenzie,Don Yeung,Matt Frank and David Kranz for attending all those practice talks and giving such good advice.I worked on some great projects with Beng-Hong Lim,Rajeev Barua,Fredrik Dahlgren,and Ricardo Bianchini(the last two,“honorary”members of the group).I also owe a lot to the interactions I have had with many other mem-bers of the lab in general.They are too numerous to list completely,but I would especially like to thank Debby Wallach,Kathy Knobe,Andr′e DeHon,Steve Keckler,Peter Nuth,Rich Lethin,Stuart Fiske,Greg Ganger,Frans Kaashoek,Charles Leiserson,Bill Weihl,Patrick

5

Sobalvarro,and Alan Edelman.Kathy Knobe,in particular,was a great neighbor and fellow traveler on the interview trail.

I would also like to thank Anne McCarthy and Jeanne Speckman,administrative assistants who were vital to the groups I’ve worked in.

I have also been fortunate to work with many people at other institutions.One of the ?rst was Shamik Sharma at Maryland,who works way too hard.Lok Liu contributed to the Remote Queues paper.John Gilbert and Shang-Hua Teng helped me with some more numerical knowledge.

Thanks to Tom Leighton and Charles Leiserson for starting the ice hockey tradition that has become such a phenomenon in our lab.I’ll miss the sport as I move to warmer climes. And to Tom Simon,hockey fanatic and long-time of?ce-mate,may your skates never rust and your gear never walk away on its own.

Thanks to my family,especially my little sister.

Above all,thanks to Debby.

This research was supported in part by an Of?ce of Naval Research Graduate Fellowship, by ARPA contract N00014-94-1-0985by NSF grant MIP-9504399,by NSF Experimental Systems grant MIP-9012773,by an NSF Presidential Young Investiga …… 此处隐藏：17489字，全部文档内容请下载后查看。喜欢就下载吧 ……