Title: Efficient Schemes for Distributing Data on Parallel Memory
Systems

Speaker: Prof. Cristina Pinotti, Univ of Pisa, Italy

Abstract:

A perfect memory system should supply immediately any datum requested
by the CPU. However, since such an ideal memory is not practically
feasible, this goal is commonly approximated by organizing the memory
hierarchically and using a parallel memory system consisting of several
modules (e.g. main memory banks and/or I/O disks) at each level of the
hierarchy.  In this talk, we discuss efficient data distribution
schemes as a technique for improving the performance of a parallel
memory system.  The objective is to fetch specific subsets of nodes
(called templates) of a given data structure called a host, in as few
memory cycles (ideally one) as possible.  If a template to be retrieved
is stored in a single memory module, its nodes can only be fetched
sequentially, one after the other, thus incurring a high access
latency. This is independent of the number of memory modules, and hence
the potential bandwidth, available in the parallel memory system.
Therefore, our goal is to evenly distribute the nodes of a host data
structure among the memory modules in such a way that the number of
nodes of a given template assigned to the same module is minimized.
Interestingly, to retrieve a template in just one cycle (i.e., without
conflicts), the lower bound on the number of memory modules required is
often greater than the template size (in terms of number of nodes).

After defining the data access problem and the optimality criteria, we
propose efficient schemes for conflict-free access to path templates
and subtrees in k-ary trees and binomial trees.  The proposed
assignments are based on simple node-indexing, modular arithmetic or
graph-theoretic techniques. Our assignments are optimal in terms of the
number of memory modules required and also balance the memory load
among the modules.