Browse Prior Art Database

Device for Performing Efficient Task-Distribution Synchronization

IP.com Disclosure Number: IPCOM000099665D
Original Publication Date: 1990-Feb-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 3 page(s) / 127K

Publishing Venue

IBM

Related People

Heidelberger, P: AUTHOR [+3]

Abstract

The task-distribution problem for parallel computer systems is the following problem. Suppose that some subset of k processors of an N-processor system requests tasks to perform, and the requests are received concurrently by a task controller. The objective is to parcel out tasks to these processors in a time that is independent of the number of requesters. It is sufficient to generate an interval of k integers, and to report a distinct integer in the interval to each requester. The device described parcels out distinct integers to requesting processors in a parallel processing system.

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

Device for Performing Efficient Task-Distribution Synchronization

       The task-distribution problem for parallel computer
systems is the following problem.  Suppose that some subset of k
processors of an N-processor system requests tasks to perform, and
the requests are received concurrently by a task controller.  The
objective is to parcel out tasks to these processors in a time that
is independent of the number of requesters.  It is sufficient to
generate an interval of k integers, and to report a distinct integer
in the interval to each requester.  The device described parcels out
distinct integers to requesting processors in a parallel processing
system.

      Prior art for this work is embodied in (*), which describes a
combining switch and a special instruction called the Fetch-and-Add
instruction.  This particular embodiment has proven to be expensive,
and may possibly be too inefficient for practical exploitation.  The
new device does less of the synchronization function in specialized
hardware than does prior art, and instead provides the means for
requesting processors to do equivalent work in parallel.

      The Task-Distribution Controller The device is called a
task-distribution controller. It has one pin per processor to which
it is attached, plus a broadcast bus that attaches to every
processor.  In normal operation the device outputs to the broadcast
bus while all processors monitor the contents of the bus.  For
initialization, a single processor can gain access to the bus and
pass initialization information to the controller on this bus.

      The basic controller contains:
1.   one input-pin per processor,
2.   one port-control logic module per processor,
3.   a memory for counters,
4.   an adder capable of forming the sum of N 1-bit numbers,
     and
5.   other random logic and internal data paths as required
     to implement the functions described below.

      The basic function of the controller is to accept requests for
task allocation and to respond to those requests.  Each processor
signals a request for task allocation of a specific type on the input
pin assigned to the processor.  The controller acts on the collection
of requests by selecting some subset of requests that are all of the
same type.  After selecting this subset, the controller produces
task- allocation information on the broadcast bus.

      The following descriptions indicate how the several functions
are implemented by the controller.

      Processor Requests Each processor places a request by encoding
the request as a serial bit-stream that is transmitted to that
processor's input pin on the controller.  The contents of the request
indicates which type of task allocation (or equivalently, the address
in the controller's memory of the current state of the task
allocation), and whether the processor is initiating the task or
terminating the task. The current state of task allocation...