Browse Prior Art Database

A STOCHASTIC MODEL OF PARALLEL AND CONCURRENT PROGRAM EXECUTION ON MULTIPROCESSORS

IP.com Disclosure Number: IPCOM000128444D
Original Publication Date: 1982-Oct-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Makrucki, B.A.: AUTHOR [+4]

Abstract

This report summarizes a model developed to allow the evaluation of parallel program execution on multiprocessors. The model is intended for MIMD algorithms in which the individual processors are coupled through their programs' interaction with memory. The model is not intended for SIMD algorithms. Specifically, estimates of processor utilization, execution times of programs or subprograms, and memory bandwidth can be obtained from the model. Earlier research has concentrated on the last of these quantities and a body of research, which might be termed ";memory interference models";, has evolved. The work reported here goes one step further by allowing the programs to be included in the model. Consequently questions about the performance of the processors running the programs can also be answered.

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

Page 1 of 38

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

A STOCHASTIC MODEL OF PARALLEL AND CONCURRENT PROGRAM EXECUTION ON MULTIPROCESSORS

B. A. Makrucki
T. N. Mudge

CRL-TR-3-82

OCTOBER 1982

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY1 Room 1079, East Engineering Building
Ann Arbor, Michigan 48109
USA
Tel: (313) 763 8000

ABSTRACT

This report summarizes a model developed to allow the evaluation of parallel program execution on multiprocessors. The model is intended for MIMD algorithms in which the individual processors are coupled through their programs' interaction with memory. The model is not intended for SIMD algorithms. Specifically, estimates of processor utilization, execution times of programs or subprograms, and memory bandwidth can be obtained from the model. Earlier research has concentrated on the last of these quantities and a body of research, which might be termed "memory interference models", has evolved. The work reported here goes one step further by allowing the programs to be included in the model. Consequently questions about the performance of the processors running the programs can also be answered.

TABLE OF CONTENTS

1. Introduction.....1
1.1. Modeling vs. Simulation and Program Testing.....3
1.2. Previous Results.....5
1.2.1. Discrete Time Models.....5
1.2.2. Continuous Time Models.....6
1.3. General Modeling Ideas.....7

2. System Configuration and Operation.....8
2.1. System Configuration.....9
2.2. System Operation.....12

3. The Semi-Markov Process (SMP) Model.....17

1 Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reject the vicars of the funding agencies.

University of Michigan Computing Research Laboratory Page 1 Oct 01, 1982

Page 2 of 38

A STOCHASTIC MODEL OF PARALLEL AND CONCURRENT PROGRAM EXECUTION ON MULTIPROCESSORS

3.1. Processor/Program Modeling.....17
3.2. Performance Measures.....22
3.2.1. Program Execution Time.....23
3.2.2. Processor Utilization.....24
3.2.3. Memory Utilization.....26
3.2.4. Connection Bandwidth.....26
3.2.5. Queue Lengths.....28
3.3. SMP Model Parameters.....29

4. Fundamental SMP Relationships..... . Measure Derivation in the SOP Model.....36
5.1. Program Execution Time.....38
5.2. Processor Utilization.....41
5.3. Memory Utilization.....41
5.3.1. The Product Form Approximation (PFA).....42
5.3.2. The Sum Form Approximation (SFA.....43
5.4. Connection Bandwidth.....44
5.5. Queue Lengths.....45

6. Computation of Sojourn Times.....46
6.1. The Independent SOP Approximation for Sojourn Times.....46
6.2. The Simple M/G/1 Computation of Sojourn Times.....49

7. Examples and Simulations.....56
7.1. Two State Model of Processor Behavior.....56
7.2. The Instruction Storage Example.....62
7.3. State Space Generator Example.....66

8. Conclusion.....74
8.1. Process Communication.....75
8.2. Transient Analysis.....75
8.3. Non-stochastic and Synchronized Systems.....75
8.4. Error...