Browse Prior Art Database

Technique for Priority Resolution in Networks That Support Parallel Synchronization

IP.com Disclosure Number: IPCOM000099391D
Original Publication Date: 1990-Jan-01
Included in the Prior Art Database: 2005-Mar-14
Document File: 6 page(s) / 202K

Publishing Venue

IBM

Related People

Stone, HS: AUTHOR

Abstract

The technique described is a priority resolution scheme is to be used in the context of a multilevel combining switch, and could be used in either a hardware or software implementation of such a switch. The objective is obtain more combining and thus high synchronization throughput by making the combination of requests likely to occur.

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

Technique for Priority Resolution in Networks That Support Parallel Synchronization

       The technique described is a priority resolution scheme is
to be used in the context of a multilevel combining switch, and could
be used in either a hardware or software implementation of such a
switch.  The objective is obtain more combining and thus high
synchronization throughput by making the combination of requests
likely to occur.

      A technique has been presented for parallel synchronization
based on the use of an instruction called Fetch-and-Add coupled with
a network of switches of a type known as a combining switch.
Although this proposal has the potential of removing a class of
synchronization bottlenecks that appear in multiprocessor networks,
it has two disadvantages - high cost and many levels of logic delay.

      Some of the disadvantages of the proposal in [*] can be
overcome by implementing some of the actions of the Fetch-and-Add in
software rather than in hardware.  The software synchronization
scheme is comprised of:
    1.  a hardware method for synchronization,
    2.  a software technique for combining,
    3.  an adaptation of the synchronization method suitable for
    crossbar switches, and
    4.  a different adaptation of the idea for multilevel switching
    networks.
    In the various adaptations of the synchronization technique, the
synchronization hardware arbitrates a pair of simultaneous requests
by returning a condition Synch Wait to one request and Synch Continue
to the other.  The purpose of this proposal is to demonstrate a way
of determining which request receives Synch Wait and which request
receives Synch Continue.  The arbitration rule tends to enhance
parallelism and increase the probability of combining future
requests. The following discussion gives the arbitration rule and
demonstrates the validity of the rule in the context of a network for
parallel synchronization. Arbitration Rule

      The hardware structure is shown in Fig. 1.  The interconnection
network is any network that routes requests from the N processors to
the two inputs of a synchronizer module.  The synchronizer in the
figure returns one of three responses to the synchronization requests
that it receives.

      1. No Synch.  No other processor is attempting to synchronize
at the same synch address in the current cycle.

      2. Synch Continue.  Another processor is attempting to
synchronize at the same synch address.  That processor has suspended
its activity and is waiting for this processor to release it.

      3. Synch Wait.  Another processor is attempting to synchronize
at the same synch address.  Suspend this processor's activity
immediately, and wait for the other processor to release this
processor before proceeding.

      To obtain access to a shared variable, processors issue log2 N
requests, as indicated in Fig. 2.  The numbers at the top of the
sync...