Browse Prior Art Database

Priority-Resolution Mechanism for Reducing Collisions in a Multi Processor Interconnection Network

IP.com Disclosure Number: IPCOM000036200D
Original Publication Date: 1989-Sep-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 4 page(s) / 52K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

A priority-resolution mechanism is used to resolve collisions in an interconnection network in a manner that tends to reduce the probability of a future collision. The mechanism tends to increase the effective bandwidth of an interconnection network.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 4

Priority-Resolution Mechanism for Reducing Collisions in a Multi Processor Interconnection Network

A priority-resolution mechanism is used to resolve collisions in an interconnection network in a manner that tends to reduce the probability of a future collision. The mechanism tends to increase the effective bandwidth of an interconnection network.

In multiprocessor systems that share a global memory, contention occurs when two or more processors attempt a concurrent access to the same memory, or attempt a concurrent use of the same connection point to memory. Fig. 1 shows a system of N processors connected to N memories through an interconnection network that is not specified in the network. If two processors attempt to reach the same memory concurrently, one of the requests must be queued while the other proceeds, because one memory can process at most one request at a time. In Fig.

(Image Omitted)

1, if both Processors 1 and 2 attempt to access Memory 4 at the same time, a collision occurs, forcing one of the requests to wait.

Even if Processors 1 and 2 access different memories, say Memories 3 and 4, respectively, a collision can occur within the interconnection network if the requests both require the use of the same internal node at the same time. When a collision occurs, one request waits while the other proceeds. This property is true of many interconnection structures, but some structures support collision- free communication because they permit requests to be routed on an alternate route rather than queued.

The mechanism described here tends to reduce collisions in multiprocessor memory systems and in some interconnection networks. The mechanism is not applicable to networks that are collision-free, nor does it apply to all possible networks in which collisions occur.

For this discussion we assume that the mechanism decides which of two requests is forwarded and which is queued. In general, collisions involving more than two requests are resolved either by 1. using two-request resolvers as basic building

blocks to create

a network that can resolve more than two colliding

requests,

or

2. generalizing the idea as described here for two

requests to

treat N requests. (The generalization is

straightforward.)

The mechanism has two facets.

1. Each request carries with it a priority that is

determined as

described below.

1

Page 2 of 4

2. At a memory or at a node in the interconnection

network at

which a collision occurs, if the requests carry

different

priorities, then the request with the higher

priority is

granted. Otherwise, ties are broken in an

arbitrary but

unbiased manner.

First we describe how a priority is established for a request, then we discuss why this priority tends to reduce collisions. Finally, we show the block diagram of a device that uses priority to resolve collisions. Priority Creation

For crossbar networks, a collection of N requests is collision- free if and only if the requests are some permutation of N m...