Avoiding memory contention on tightly coupled multiprocessors

Author

Valerio, M. ; Moser, L.E. ; Melliar-Smith, P.M.

Author_Institution

Dept. of Electr. & Comput. Eng., California Univ., Santa Barbara, CA, USA

fYear

1994

fDate

2-6 May 1994

Firstpage

643

Lastpage

654

Abstract

We propose a novel method of scheduling memory access on a non blocking interconnection network that provides only one-to-one communication. Conflicts at the switches can be avoided if the accesses are scheduled so that no two processors attempt to access the same memory at the same time. We show how such a scheduling problem can be mapped to an edge coloring problem for a directed graph and present algorithms for solving that problem. We give examples of the application of the algorithm and present simulation results

Keywords

directed graphs; graph colouring; multistage interconnection networks; processor scheduling; storage management; directed graph; edge coloring problem; memory access; memory contention; non blocking interconnection network; one-to-one communication; scheduling; simulation results; tightly coupled multiprocessors; Application software; Communication switching; Computer networks; Concurrent computing; Multiprocessor interconnection networks; Processor scheduling; Read-write memory; Scheduling algorithm; Switches; Writing;

fLanguage

English

Publisher

ieee

Conference_Titel

Massively Parallel Computing Systems, 1994., Proceedings of the First International Conference on

Conference_Location

Ischia

Print_ISBN

0-8186-6322-7

Type

conf

DOI

10.1109/MPCS.1994.367023

Filename

367023