Link to the University of Pittsburgh Homepage
Link to the University Library System Homepage Link to the Contact Us Form


Shao, Shuyi (2011) COMPILER TECHNIQUES FOR EFFICIENT COMMUNICATIONS IN MULTIPROCESSOR SYSTEMS. Doctoral Dissertation, University of Pittsburgh. (Unpublished)

Primary Text

Download (1MB) | Preview


Technical advances have brought circuit switching back to the stage of interconnection network design for high performance computing. Although circuit switching has long connection establishment delays and the dedication of connections prevents other communicating nodes from sharing the network, it has simple control logic and significant cost advantage over packet or wormhole switching. With the proper assistance from compilers, circuit switching has the potential of providing significant performance benefits when connections can be established prior to the actual communication. This dissertation presents a novel compilation framework for achieving efficient communications in circuit switching interconnection networks. The goal of the framework is to identify communication patterns in Single-Program-Multiple-Data (SPMD) parallel applications and compile these patterns as network configuration directives. This can significantly reduce the communication overhead on circuit switching interconnection networks. A powerful representation scheme is developed in this research to capture the property of communication patterns and allow manipulation of these patterns. Based on the temporal and spatial localities of communications and the capability of the compiler to identify the communication patterns, we classify communication patterns into three categories - static, persistent, and dynamic. We target static and persistent communications, which are dominant in most parallel applications. To identify communication patterns, we develop a novel symbolic expression analysis. We develop certain compiler techniques for analyzing communication patterns. Since the underlying network capacity is limited, we develop an algorithm to partition the program into phases based on the communication requirements and network capacity. To demonstrate the effectiveness of our framework, we implement an experimental compiler. The compiler identifies the communication patterns from the source code, partitions the program into phases, and inserts the network configuration directives at phase boundaries to achieve efficient communications. The compiler also can generate communication traces, which provides useful information about the communication pattern correlated to the structure of the source code. We develop a multiprocessor system simulator to evaluate our techniques. Our simulation-based performance analysis demonstrates that using our compiler techniques can achieve the same level, or even better level of communication performance than fast packet switching networks while using much less expensive circuit switches.


Social Networking:
Share |


Item Type: University of Pittsburgh ETD
Status: Unpublished
CreatorsEmailPitt UsernameORCID
Shao, Shuyishs2@pitt.eduSHS2
ETD Committee:
TitleMemberEmail AddressPitt UsernameORCID
Committee ChairMelhem, Ramimelhem@cs.pitt.eduMELHEM
Committee CoChairJones, Alex Kakjones@pitt.eduAKJONES
Committee MemberCho, Sangyeuncho@cs.pitt.eduSANGYEUN
Committee MemberZhang, Youtaozhangyt@cs.pitt.eduYOUTAO
Date: 30 January 2011
Date Type: Completion
Defense Date: 6 December 2010
Approval Date: 30 January 2011
Submission Date: 2 December 2010
Access Restriction: No restriction; Release the ETD for access worldwide immediately.
Institution: University of Pittsburgh
Schools and Programs: Dietrich School of Arts and Sciences > Computer Science
Degree: PhD - Doctor of Philosophy
Thesis Type: Doctoral Dissertation
Refereed: Yes
Uncontrolled Keywords: Communication Pattern; Compiled Communication; High Perofrmance Computing; MPI; Multiprocessor Systems; Multiprocessor Systems Simulator
Other ID:, etd-12022010-225204
Date Deposited: 10 Nov 2011 20:07
Last Modified: 15 Nov 2016 13:52


Monthly Views for the past 3 years

Plum Analytics

Actions (login required)

View Item View Item