Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!mips!apple!amdahl!JUTS!rbw00
From: rbw00@ccc.amdahl.com (  213  Richard Wilmot)
Newsgroups: comp.arch
Subject: Re: Floating Point Risc
Keywords: Fractional Addressing
Message-ID: <08yL020i07aF01@JUTS.ccc.amdahl.com>
Date: 23 Apr 91 15:48:55 GMT
References: <1991Apr20.063947.12811@sbcs.sunysb.edu> <41518@cup.portal.com>
Reply-To: rbw00@JUTS.ccc.amdahl.com (  213  Richard Wilmot)
Organization: Amdahl Corporation, Sunnyvale CA
Lines: 59

In article <41518@cup.portal.com> mmm@cup.portal.com (Mark Robert Thorson) writes:
>How about addressing memory using addresses similar to the Dewey decimal
>system?  This numbering system allows you to insert an arbitrary number
>of entries in any arbitrary place, without disturbing the rest of the
>numbering system.  E.g. if you want to put something between 11.44.008
>and 11.44.009, you can just create a new address 11.44.008.01.  The
>Xanadu hypertext project is using a similar number system.
>
>This feature would allow you to insert into a list without having any links.
>No pointers ever have to be moved.

I proposed such a system at a symposium on high performance transaction
systems in 1985 (or was it 1987?) for quickly doing large volumes of 
transactions. There were some pretty knowledgeable experts there on
both transaction systems and computer architecture but that was the beginningg
of the RISC phase so either it was a dumb idea, or it was swamped by
RISC religion, or they didn't understand what I was trying to do.

I still like the idea and, with larger numbers of transistors becoming
available it may get another chance. It solved several problems in
a transaction system:

 o  The addressing in memory could be by hashing (with hardware)
    while that on disk might be organized in a B*-Tree. The slower
    outboard data structuring could then be easily offloaded to
    another processor (parallelism).

 o  The addressing in caches is already by hashing so all we need do
    is use the right bits out of the generated address for that hashing
    so as to keep collisions and false sharing low.

 o  Locking seems to be a necessary database/transaction operation.
    It too could be done in parallel by another engine and perhaps
    more efficiently. Present systems seem to use upwards of 500-1,500
    instructions to lock an object (row, page, table). B-Trees are
    often worse because under updates the locks must propagate up the
    tree as high as higher keys must be changed in the tree. Locking
    can proceed in parallel so long as no changes are committed before
    we are assured that this transaction got the lock and also could
    have gotten the lock at the time a data item is fetched from
    memory.

 o  Journalling/logging is also required in most transaction systems
    and this too could be done in parallel.

 o  Most helpful, perhaps, is that between any two existing objects
    we can now squeeze (with fractional addressing) as many new objects
    as we wish. Addresses will get longer but the part used for cache
    addressing will not. Then, unlike B-Trees, we can stash new objects
    without consulting the existing structure.

The basic principle is that addresses can (and are sometimes) be used for
many different purposes/emphases and with the right, flexible addressing 
scheme we can use the same addresses for these different purposes at
the same time in parallel.

-- 
  Dick Wilmot  | I declaim that Amdahl might disclaim any of my claims.
                 (408) 746-6108