Browse Prior Art Database

MEMORY INTERFERENCE MODELS WITH VARIABLE CONNECTION TIME

IP.com Disclosure Number: IPCOM000128477D
Original Publication Date: 1984-Jul-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Mudge, T.N.: AUTHOR [+4]

Abstract

This paper develops two discrete time models of the interference that occurs during memory access in multiprocessor systems. These models, the equivalent rate model and the Markov chain model, provide for variable connection times between processors and memories it these times can be characterized by a discrete random variable, X, with a probability mass function f(i). Neither model requires a complete description of f(i). The equivalent rate model, which is the simpler, requires only the first moment, while the Markov chain model requires the first and second moments. The models yield estimates of the bandwidth, BW, and related measures such as the probability that a memory request is accepted, P a , and processor utilization, U p . A brief summary of earlier discrete time models is included, and it is shown that one of them is a proper special case of the Markov chain model. Comparisons with simulations show that both models give good estimates of BW when the coefficient of variation, C v , of X is small. When C v reaches 2.0 the Markov chain model still shows an error of less than 4% while the equivalent rate model exhibits a 50% error that, unlike the Markov chain model, continues to increase with increase in C v . Finally, it is shown that BW drops significantly with increase in C v , suggesting that processor-memory transfers should use a fixed block size it memory conflict is to be minimized.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 7% of the total text.

Page 1 of 15

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

MEMORY INTERFERENCE MODELS WITH VARIABLE CONNECTION TIME

T.N. Mudge and Humoud B. Al-Sadoun

CRL-TR-16-84

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 JULY 1984 (Revision 1)

Room 1079, East Engineering Building

Ann Arbor, Michigan 48109
USA
Tel: (313) 763-8000

MEMORY INTERFERENCE MODELS WITH VARIABLE CONNECTION TIME by T. N. Mudge and Humoud B. Al-Sadoun
Computing Research Lab
Department of Electrical Engineering and Computer Science The University of Michigan
Ann Arbor, MI 48109 313/764-0203

Abstract

This paper develops two discrete time models of the interference that occurs during memory access in multiprocessor systems. These models, the equivalent rate model and the Markov chain model, provide for variable connection times between processors and memories it these times can be characterized by a discrete random variable, X, with a probability mass function f(i). Neither model requires a complete description of f(i). The equivalent rate model, which is the simpler, requires only the first moment, while the Markov chain model requires the first and second moments. The models yield estimates of the bandwidth, BW, and related measures such as the probability that a memory request is accepted, Pa, and processor utilization, Up. A brief summary of earlier discrete time models is included, and it is shown that one of them is a proper special case of the Markov chain model. Comparisons with simulations show that both models give good estimates of BW when the coefficient of variation, Cv, of X is small. When Cv reaches 2.0 the Markov chain model still shows an error of less than 4% while the equivalent rate model exhibits a 50% error that, unlike the Markov chain model, continues to increase with increase in Cv. Finally, it is shown that BW drops significantly with increase in Cv, suggesting that processor-memory transfers should use a fixed block size it memory conflict is to be minimized.

Index terms -- Memory Interference, Multiprocessors, Memory Bandwidth, Performance Evaluation, Markov Chains.

This work was supported in part by National Science Foundation under Grant MCS~8009315.

1 This work was supported in part by National Science Foundation under Grant MCS-8009315. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the funding agencies.

University of Michigan Computing Research Laboratory Page 1 Jul 01, 1984

Page 2 of 15

MEMORY INTERFERENCE MODELS WITH VARIABLE CONNECTION TIME

1. Introduction

This paper develops two discrete time models of the memory interference that occurs during memory access in a multiprocessor system. These models, termed the equivalent rate (ER) model and the Markov chain (MC) model, are based on a set of assumptions that characterize the memory access behavior of a multiprocessor system as a stochastic process. Figure 1 ill...