🚀 go-pugleaf

              The International Computer Science Institute
                     is pleased to present a talk:

                  Thursday, August 13, 1992  2:00 p.m.

                              ANDREW CHIN
                       Department of Mathematics
                         Texas A & M University

               ``Locality-Preserving Hash Functions for
                  General Purpose Parallel Computation''

           Consider the  problem  of  efficiently  simulating  the
      shared-memory parallel random access machine (PRAM) model on
      massively parallel architectures with physically distributed
      memory.  To  prevent network congestion and memory bank con-
      tention, it may be advantageous to hash  the  shared  memory
      address space. The decision on whether or not to use hashing
      depends on two factors: the  communication  latency  in  the
      network,  and  the  locality of memory accesses in the algo-
      rithm.

           We relate this decision directly to algorithmic  issues
      by  studying  the  complexity  of  hashing in the Block PRAM
      model of Aggarwal, Chandra and Snir, a  shared-memory  model
      of  parallel  computation  which  accounts for communication
      locality. In particular, we present a  universal  family  of
      hash  functions  having  optimal  locality. A consequence of
      this result is that hashing and randomized routing need  not
      destroy locality, addressing an open question of Valiant.


        This talk will be held in the Main Lecture Hall at ICSI.
          1947 Center Street, Sixth Floor, Berkeley, CA 94704
       (On Center between Milvia and Martin Luther King Jr. Way)

       ----------------------------------------------------------
       Requests to be added to or deleted from the "talk" mailing
       list should be directed to talk-request@icsi.Berkeley.EDU.
       ----------------------------------------------------------