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

Leapfrog Problem in Combining Networks and Its Solution

IP.com Disclosure Number: IPCOM000121138D
Original Publication Date: 1991-Jul-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 2 page(s) / 99K

Publishing Venue

IBM

Related People

Brantley, W: AUTHOR [+6]

Abstract

Multistage interconnection networks provide a means of interconnecting processing elements (PEs) and memory modules (MMs) of multiprocessor systems. The interconnection consists of one or more stages of switches, typically, consisting of n inputs and n outputs. Because of conflicts within the network (i.e., more than one request is routed to the same output of a switch) output first-in, first-out (FIFO) queues are (generally) associated with each output port of a switch. If several requests are destined to the same memory location (termed a hot spot), a switch's FIFOs may fill up and cause a backup in the network.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Leapfrog Problem in Combining Networks and Its Solution

      Multistage interconnection networks provide a means of
interconnecting processing elements (PEs) and memory modules (MMs) of
multiprocessor systems.  The interconnection consists of one or more
stages of switches, typically, consisting of n inputs and n outputs.
Because of conflicts within the network (i.e., more than one request
is routed to the same output of a switch) output first-in, first-out
(FIFO) queues are (generally) associated with each output port of a
switch.  If several requests are destined to the same memory location
(termed a hot spot), a switch's FIFOs may fill up and cause a backup
in the network.

      Combining memory requests has been proposed as a solution to
reducing contention and memory latency in multiprocessor systems
employing multistage interconnection networks.  The combining of
memory requests is performed within the network switches.  A memory
request issued by a PE usually consists of, at least, the requesting
PE address, the memory address and the operation code.  When a new
request enters a switch node, it is compared with requests already
queued in the FIFO.  The comparison is usually done on the operation
code and the memory address. If these match, the two requests are
combined and only one request is sent out to the next stage or the
memory module.

      Unless complete heterogeneous combining is done (i.e., requests
are combined independent of the operation code) a PE request can jump
ahead of a previously issued request from the same PE, termed
leapfrogging.  This can violate the uniprocessor order (memory
operations to the same memory location must occur in the order
determined by the program being executed on the PE).  Consider the
case when only like operation codes are combined:  shown in Figure 1
is a sample instruction flow from one PE.  If the first LOAD and the
STORE are...