Title

Exploring virtual network selection algorithms in DSM cache coherence protocols

Authors

Authors

M. Chaudhuri;M. Heinrich

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Abbreviated Journal Title

IEEE Trans. Parallel Distrib. Syst.

Keywords

distributed shared memory; cache coherence protocol; virtual network; deadlock-freedom; MULTIPROCESSOR; PERFORMANCE; Computer Science, Theory & Methods; Engineering, Electrical & Electronic

Abstract

Distributed shared memory (DSM) multiprocessors typically require disjoint networks for deadlock-free execution of cache coherence protocols. This is normally achieved by implementing virtual networks with the help of virtual channels or virtual lanes multiplexed on a single physical network. To keep the coherence protocol simple, messages are usually assigned to virtual lanes in a predefined static manner based on a cycle-free lane assignment dependence graph. However, this static split of virtual networks ( such as request and reply networks) may lead to underutilization of certain virtual networks while saturating the other networks. In this paper, we explore different static and dynamic schemes to select the virtual lanes for outgoing messages and mix the load among them without restricting any particular type of message to be carried only by a particular virtual network. We achieve this by exposing the selection algorithms to the coherence protocol itself, so that it can inject messages into selected virtual lanes based on some local information, and still enjoy deadlock-freedom. Our execution-driven simulation on five applications from the SPLASH-2 suite shows that as the system scales, the virtual network selection algorithms play an important role. For 128-node systems, our dynamic selection algorithm speeds up parallel execution by as much as 22 percent over an optimized baseline system running a modified SGI Origin 2000 protocol. We also explore how network latency, the number of message buffers per virtual lane, and the depth of network interface output queues affect the relative performance of various virtual lane selection algorithms.

Journal Title

Ieee Transactions on Parallel and Distributed Systems

Volume

15

Issue/Number

8

Publication Date

1-1-2004

Document Type

Article

Language

English

First Page

699

Last Page

712

WOS Identifier

WOS:000222073200003

ISSN

1045-9219

Share

COinS