Browse Prior Art Database

Forking Queue

IP.com Disclosure Number: IPCOM000121216D
Original Publication Date: 1991-Aug-01
Included in the Prior Art Database: 2005-Apr-03
Document File: 4 page(s) / 112K

Publishing Venue

IBM

Related People

Bergey Jr, AL: AUTHOR

Abstract

Some computer designs require forking of data where data from one source is simultaneously transmitted to two destinations. This invention is a queue that performs forking. It is a single design which performs forking and buffers data at lower cost than conventional designs, which implement forking logic and buffering queues separately.

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

Forking Queue

      Some computer designs require forking of data where data
from one source is simultaneously transmitted to two destinations.
This invention is a queue that performs forking.  It is a single
design which performs forking and buffers data at lower cost than
conventional designs, which implement forking logic and buffering
queues separately.

      Forking, a data transfer operation in which a field of data is
simultaneously sent to two destinations, is required in many computer
designs.  For example, a cached DASD control unit may route data from
a DASD (Direct Access Storage Device) simultaneously to the host and
to the cache. Data from a host may simultaneously be routed to the
DASD and to the cache.

      Conventional FIFO (first-in, first-out) queues have been used
extensively in the prior art.  Fig. 1 shows an example of the
structure of a prior-art FIFO queue.  This conventional queue
contains the following components, shown in Fig. 1:
      1.  Array.  Buffers the data.
      2.  An "In Pointer" associated with the filling process.  This
determines the array address used to store data.
      3.  An "Out Pointer" associated with the emptying process. This
determines the array addresses used to fetch data.
      4.  An incrementer used to increment a pointer after it is
used.
      5.  A set of compare logic.  This comparator compares the
filling pointer with the emptying pointer.
      6.  A set of empty/full logic.  This uses the output of the
compare logic to determine whether the queue is full, empty or in
between.
      7.  One data source.
      8.  One data destination.

      The two-port queue follows the prior-art algorithms for a FIFO
queue.  These algorithms are the data store algorithm:
?if((Data from source is available) AND
 (queue is not full)) then
   ?do;
      Store data into location specified by filling pointer;
      Increment filling pointer;
      ?If filling pointer equals emptying pointer, queue is full.
          ?else queue is neither full nor empty.
      Update empty/full logic;
      ?end;
and the data fetch algorithm:
?If ((Data destination can accept data) AND
      (queue is not empty)) then
     ?do;
      Fetch data from location specified by emptying pointer;
      Increment emptying pointer;
      ?if filling pointer equals emptying pointer, queue is empty.
          ?else queue is neither full nor empty.
      ?end;

      The invention is a queue with three ports.  It creates the
effect of two queues, but because much of the logic is shared between
the two queues, it costs less than two independent queues.  The queue
contains the following components, which are shown in Fig. 2:
      1. Array.  Buffers the data.
      2. An "In Pointer" associated with the filling process. This
determines the array address used to sto...