Browse Prior Art Database

Algorithm for a Compressed Data Bus for Multiprocessors

IP.com Disclosure Number: IPCOM000122804D
Original Publication Date: 1998-Jan-01
Included in the Prior Art Database: 2005-Apr-04
Document File: 6 page(s) / 180K

Publishing Venue

IBM

Related People

Malik, N: AUTHOR [+3]

Abstract

Disclosed is an algorithm which may be used to compress databus transfers in conventional Symmetric Multiprocessor Computers of today which should ease the communication bandwidth problem.

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

Algorithm for a Compressed Data Bus for Multiprocessors

      Disclosed is an algorithm which may be used to compress databus
transfers in conventional Symmetric Multiprocessor Computers of today
which should ease the communication bandwidth problem.

      Data compression

      A compression algorithm is proposed which is trivial to
calculate in both directions and which may be used effectively in a
multiprocessor system to raise the effective communication bandwidth
along a data channel between processing elements.

      Typical data bus communication is comprised predominantly of a
data transfer which source and destination are cache lines (or
perhaps a memory line) which are of a size several times greater than
the data bus  width.  Cache line transfers will appear as consecutive
flits on the databus.  It is not difficult to convince oneself that
the data items which are declared in any typical program as an
integer or enumerated type have a relatively small, finite range of
values which they may take in any correct execution of the program.
For a large class of applications (both parallel and
single-threaded), these "overrepresented  integer types" will
represent a significant percentage of the total data  associated with
the program.  Further, they will also represent a large  percentage
of the data transfers that occur on the data bus in a multiprocessor
which executes that program.  High-level-language compilers (to
satisfy performance constraints that arise due to typical  processor
construction) will align data types in memory to the size of  the
data type.  Thus, one may safely conclude that data flits on a data
bus which represent communication between threads of a program
written in a high-level language will contain data types which are
also aligned with  the flit itself.

      The end result: the flits on the data bus frequently have a
large number of zeroes which occur in a very predictable pattern.

      A compression algorithm

      Any compression algorithm used on a data bus in a
multiprocessor system must be nearly trivial to calculate.  Here, a
compression algorithm is proposed that can be made quite simple to
calculate at both ends of the data transfer and which capitalizes on
the assertions above about the characteristics of the data flits
which appear on a data bus.

This scheme incurs at least two costs which should be acknowledged in
advance:
  1.  The bit width of the data bus will be expanded by a number
       of pins.  This number of pins may be determined as a design
       parameter.  The tradeoff is effectiveness of the algorithm.
  2.  The latency through the communication path will be increased.
       The increase can be made insignificant with respect to the
       existing latency, given careful implementation of the
       compression algorithm in hardware.

      The compression algorithm, written in a simple, iterat...