Browse Prior Art Database

Reordering Out-of-Order Transfer in Computer I/O

IP.com Disclosure Number: IPCOM000111658D
Original Publication Date: 1994-Mar-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 6 page(s) / 222K

Publishing Venue

IBM

Related People

Sachs, MW: AUTHOR

Abstract

With some I/O devices and interconnection systems, data can be transferred unpredictably out of the logical order assumed by the program. Examples are some proposed array DASD configurations and misordered data delivery in the connectionless modes of the ANSI Fibre Channel Standard. Reordering of received data can have a severe performance penalty.

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

Reordering Out-of-Order Transfer in Computer I/O

      With some I/O devices and interconnection systems, data can be
transferred unpredictably out of the logical order assumed by the
program.  Examples are some proposed array DASD configurations and
misordered data delivery in the connectionless modes of the ANSI
Fibre Channel Standard.  Reordering of received data can have a
severe performance penalty.

      In this article, we use the term "unit of data"  to refer to a
collection of bytes transferred in logical order which occupies a
contiguous portion of the logical data stream as viewed by the
program and therefore is to be stored in a contiguous area of the
logical buffer.  Examples of a unit of data are a single DASD block
and the payload of a single transmission frame in the case of a
misordering interconnection network.

      A typical I/O request consists of a command to the device and a
list of one or more buffer descriptors, which we call a buffer list.
As a result of the command, data are transferred either from the
buffers described by the buffer list to the device or from the device
to the buffers described by the buffer list.  Each descriptor (buffer
list entry or BLE) contains a buffer address and the length of the
buffer (typically in bytes).  requestple of such a request structure
is the IBM System/390* channel program architecture, in which the
buffer list is a group of data-chained channel command words (CCWs).

      There are two cases of misordered data.  In the first case, the
program knows the size of the unit of data.  In the second case, the
program does not know the size of the unit of data.

      An example of the case where the size of the unit of data is
known by the program is DASD data.  We use the term "block"  or "disk
block"  interchangeably with "unit of data." To enable the channel
program to control reordering of the data, each unit of data, or
group of consecutive, contiguous, units of data, is labelled with the
block number of the logical block (or the first logical block in the
group) in the file on the I/O device.  It will be noted that an
alternative form of label would contain the starting byte number
rather than a block number.  Because the buffer list may not be in
contiguous storage, the block number does not directly give the
buffer list entry address.  Therefore, we use a translation table
which contains the address of the buffer list entry corresponding to
each block number in the data stream.  The table structure permits
each unit of data to be described by an arbitrary number of buffer
list entries and allows the number of buffer list entries to be
different for each unit of data.  Using this table, the channel can
obtain the correct buffer list entry, given the block number, in, at
most, three main storage references, and it should be possible for
the channel to retain some look-aside information to further reduce
the average number of storage refer...