Browse Prior Art Database

Optimal Tabulation With Integrated Modules

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

Publishing Venue

IBM

Related People

Chan, SW: AUTHOR

Abstract

A new approach in tabulating item attributes optimally, using a table of integrated modules that are all of "shiftable row-widths", is disclosed. A "shiftable row-width" is a row-width value which is equivalent to some 'power' of 2. For a table having rows that are of such "shiftable row-width", the address of any row can be obtained as the sum of the pointer to the table, and the row-index "left-shifted" by the amount (in bit-positions) equal to that 'power'. Conversely, the addressing of any row in a table not having rows of "shiftable row- width" must be obtained as the sum of the table pointer, and the row- index "multiplied" by the row-width itself. Usually, "multiplication" is many times slower than "left-shifting".

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

Optimal Tabulation With Integrated Modules

      A new approach in tabulating item attributes optimally,
using a table of integrated modules that are all of "shiftable
row-widths", is disclosed.  A "shiftable row-width" is a row-width
value which is equivalent to some 'power' of 2.  For a table having
rows that are of such "shiftable row-width", the address of any row
can be obtained as the sum of the pointer to the table, and the
row-index "left-shifted" by the amount (in bit-positions) equal to
that 'power'.  Conversely, the addressing of any row in a table not
having rows of "shiftable row- width" must be obtained as the sum of
the table pointer, and the row- index "multiplied" by the row-width
itself.  Usually, "multiplication" is many times slower than
"left-shifting".  Alternatively, a table that originally did not have
"shiftable row-width" can be rounded up to one that is (with wider
"shiftable" row-width).  However, the trade-off for the shorter
table-accessing latency is "holes" in the "rounded" rows.

      The item attributes, which may total to a byte-count that is
not a power of 2, are partitioned into a collection of virtual table-
modules.  Each of these virtual modules has a "shiftable row-width".
They are organized in such a way that renders it unnecessary to store
their individual address-pointers.  The accessing of any one module
can be achieved with a latency that is as short as any simple table
with "shiftable row-width".  With this new technique, the 'holes'
introduced in rounding the attribute byte-count to a "shiftable row-
width" can be totally avoided.

      The basic idea is to partition the attributes into groups that
will fit into a set of virtual table-modules, whose rows are of
"shiftable row-widths" (refer to Fig. 1). The partitioning of the
attributes are to be carried out according to Fig. 2.  As an example,
if the attributes total to 19 bytes, then, the resulting groupings
are 16, 2, and 1, respectively.  Correspondingly, virtual
table-modules with rows of 16 bytes...