Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

QUEUEING ANALYSIS OF A CANONICAL MODEL OF REAL-TIME MULTIPROCESSORS

IP.com Disclosure Number: IPCOM000128447D
Original Publication Date: 1983-Feb-01
Included in the Prior Art Database: 2005-Sep-16

Publishing Venue

Software Patent Institute

Related People

Krishna, C.M.: AUTHOR [+4]

Abstract

Multiprocessors are beginning to be regarded increasingly favorably as candidates for controllers in critical real-time control applications such as aircraft. Their considerable tolerance of component failures together with their great potential for high throughput are contributory factors. In this report, we present first a logical classification of multiprocessor structures from the point of view of control applications. We point out that one important subclass has hitherto been neglected by the analysts. This is the class of systems with a common memory, minimal interprocessor communication and perfect processor symmetry. The performance characteristic of the greatest importance in real-time applications is the response time distribution. Indeed, we have shown in a separate report ( (2) C. M. Krishna and K. G. Shin, ";Performance Measures for Multiprocessor Controllers,"; Performance '83. Ninth Int'l Symp. on Computer Perf., Measurement and Evaluation.) how it is possible to characterize rigorously and objectively the performance of a real-time multiprocessor given the application and the multiprocessor response time distribution and component failure characteristics. We therefore present here a computation of the response time distribution for a canonical model of real- time multiprocessor. To do so, we approximate the multiprocessor by a blocking model and present a means for efficient analysis. Two separate models are derived: one created from the system's point of view, and the other from the point of view of an incoming task. The former model is analyzed along largely conventional lines. For the latter model, an artificial server is used and the system transformed into a queueing network. Validations show that the approximation is good.

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

Page 1 of 11

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

QUEUEING ANALYSIS OF A CANONICAL MODEL OF REAL-TIME MULTIPROCESSORS

C. M Krishna

K G. Shin

CRL-TR-8-83

THE UNIVERSITY OF MICHIGAN COMPUTING RESEARCH LABORATORY 1

FEBRUARY 1983

Room 1079, East Engineering Building

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

ABSTRACT

Multiprocessors are beginning to be regarded increasingly favorably as candidates for controllers in critical real-time control applications such as aircraft. Their considerable tolerance of component failures together with their great potential for high throughput are contributory factors.

In this report, we present first a logical classification of multiprocessor structures from the point of view of control applications. We point out that one important subclass has hitherto been neglected by the analysts. This is the class of systems with a common memory, minimal interprocessor communication and perfect processor symmetry.

The performance characteristic of the greatest importance in real-time applications is the response time distribution. Indeed, we have shown in a separate report 2 how it is possible to characterize rigorously and objectively the performance of a real-time multiprocessor given the application and the multiprocessor response time distribution and component failure characteristics. We therefore present here a computation of the response time distribution for a canonical model of real- time multiprocessor.

To do so, we approximate the multiprocessor by a blocking model and present a means for efficient analysis. Two separate models are derived: one created from the system's point of view, and the other from the point of view of an incoming task. The former model is analyzed along largely conventional lines. For the latter model, an artificial server is used and the system transformed into a queueing network. Validations show that the approximation is good.

TABLE OF CONTENTS

1 1 This work was supported by NASA Grant No. NAG 1- 296. 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 agency.

2 (2) C. M. Krishna and K. G. Shin, "Performance Measures for Multiprocessor Controllers," Performance '83. Ninth Int'l Symp. on Computer Perf., Measurement and Evaluation.

University of Michigan Computing Research Laboratory Page 1 Feb 01, 1983

Page 2 of 11

QUEUEING ANALYSIS OF A CANONICAL MODEL OF REAL-TIME MULTIPROCESSORS

1. Introduction.....1
2. Canonical Models of Real-Time Multiprocessors.....2
3. Response-Time Analysis of Type 1b System Without Paging.....5
3.1. Description of the Real-Time Multiprocessor.....5
3.2. System-Oriented Model.....8
3.3. Task-Oriented Model.....11
3. 4. Validation.....14
3.5. Non-exponential Service Rates.....15
4. Discussion.....16
5. References.....17

[ Chapter ] 1. Introduction

With semiconductor component costs falling and microprocessors beco...