Browse Prior Art Database

Queuing Delay Modeling for Multistage Interconnection Multiprocessor Networks

IP.com Disclosure Number: IPCOM000128194D
Original Publication Date: 1984-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 13 page(s) / 33K

Publishing Venue

Software Patent Institute

Related People

Paul G. Spirakis: AUTHOR [+3]

Abstract

We develop here a method of modeling the queuing delays in the discrete time, multistage, banyan networks (see e.g. [GL, 83]). We proceed from modeling the queuing delays of a k x k switch of the first stage of the network to deriving the queue length distribution of the switch and then we analyze the more difficult cases of the internal network stages and the case of finite buffers. We extend here the analysis for queuing delays, given in [KS, 82]. Our results are in good agreement with simulation results. For example, our results can be applied to queuing delay modeling for the Ultacomputer network (see [ GGKMItS , 82 J) .

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

Page 1 of 13

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Queuing Delay Modeling for Multistage Interconnection Multiprocessor Networks

Paul G. Spirakis

March 1984

Report #114 Ultranote: 68 ~" .-., .~. >.x ~. ..

Abstract

We develop here a method of modeling the queuing delays in the discrete time, multistage, banyan networks (see e.g. [GL, 83]). We proceed from modeling the queuing delays of a k x k switch of the first stage of the network to deriving the queue length distribution of the switch and then we analyze the more difficult cases of the internal network stages and the case of finite buffers. We extend here the analysis for queuing delays, given in [KS, 82]. Our results are in good agreement with simulation results. For example, our results can be applied to queuing delay modeling for the Ultacomputer network (see [ GGKMItS , 82 J) .

t

1. Introduction

Highly parallel computing systems seem to be the answer to the need for increased computing power. Large scale multiprocessor systems with thousands of processors have been proposed. A typical configuration for such a system is shown in Figure 1: Many identical processors are connected via an interconnection network to identical memory modules. The network supports dynamic access from each processor to each memory module. In a tightly coupled MIMD machine, the network traffic consists of small packets (requests to memory and replies), with the requests being dynamically generated independently at each processor. essentially random. The pattern of requests may be considered to be

0 . . . 0 Processors Memory Modules We consider packet switching networks built of switches connected by unidirectional lines. A k input, k output (kXk) switch can receive packets at each of its k input ports and send them through each of its k output ports. Formally, a network is a labeled digraph where nodes are of the following three types: (i) source nodes (indegree 0, outdegree 1) (ii) sink nodes (indegree 1, outdegree 0) (iii) switches (positive indegreeiand outdegree) We restrict our analysis to oblivious routing algorithms i.e. algorithms in which the path of a packet through the network is fixed at the souce node issuing it. The path can be encoded as the sequence of labels of the successive switch outputs of the path (path descriptor). Following [KS, 82], [GL, 83], we define a banyan network to be a network with a unique path from each source to each sink node. An n-stage banyan is a banyan network where the nodes can be arranged in n stages, with all the source nodes connected to switches at the first stage, and all the outputs at stage i connected to inputs at stage i+1. An n-stage rectangular banyan network of degree k is an n-stage banyan network built of k x k switches. We model here the performance of buffered banyan networks of degree k, where buffers are used in each

New York University Page 1 Dec 31, 1984

Page 2 of 13

Queuing Delay Modeling for Multistage Interconnection Mult...