Interconnection networks and compiler algorithms for multiprocessors

Lee, Kyungsook Yoon

Permalink

https://hdl.handle.net/2142/126868 Copy

Description

Title

Interconnection networks and compiler algorithms for multiprocessors

Author(s)

Lee, Kyungsook Yoon

Issue Date

1983-01-01

Keyword(s)

data movement; global memory; Benes network; parallel processor

Date of Ingest

2025-03-25T14:17:47-05:00

Abstract

In this thesis the rearrangeablity of interconnection networks and the data movement between the global memory and the processor local memory are studied. A new rearrangeability proof for interconnection networks is developed, with the same lower bound hardware requirement as the Benes network but for a general configuration. This new proof technique is universal, in the sense that it can be applied to any lower bound rearrangeable interconnection network. It is also a constructive proof which yields a control algorithm. Another problem studied is the effect of global delays on system speed, caused by the traffic between local memory and global memory in parallel processor systems. The memory bandwidth, memory conflicts and interconnection conflicts contribute to global delays. A Prefetch/Execute/Poststore pipeline is introduced to reduce the performance degradation due to global delays for innermost vector loops. The analyzing vectorizer PARAFRASE is used to measure the speedup loss on 31 scientific programs with and without the pipeline.

Publisher

Coordinated Science Laboratory, University of Illinois at Urbana-Champaign

Series/Report Name or Number

CSRD-365

Type of Resource

text

Genre of Resource

• technical report
• dissertation/thesis

Language

eng

Copyright and License Information

University of Illinois Board of Trustees

Owning Collections