Technical Report Available

[Lee Giles]

The following technical report presents the experimental results of three 
on-line learning solutions in predicting multiprocessor memory access patterns.

__________________________________________________________________________

   PERFORMANCE OF ON-LINE LEARNING METHODS IN PREDICTING MULTIPROCESSOR
                       MEMORY ACCESS PATTERNS


Majd F. Sakr (1,2), Steven P. Levitan (2), Donald M. Chiarulli (3),
              Bill G. Horne (1), C. Lee Giles (1,4)

(1) NEC Research Institute, 4 Independence Way, Princeton NJ 08540
(2) University of Pittsburgh, Electrical Engineering, Pittsburgh PA 15261
(3) University of Pittsburgh, Computer Science, Pittsburgh PA 15260
(4) UMIACS, University of Maryland, College Park, MD 20742

                             Abstract:

Shared memory multiprocessors require reconfigurable interconnection 
networks (INs) for scalability. These INs are reconfigured by an IN 
control unit. However, these INs are often plagued by undesirable 
reconfiguration time that is primarily due to control latency, the 
amount of time delay that the control unit takes to decide on a 
desired new IN configuration. To reduce control latency, a trainable 
prediction unit (PU) was devised and added to the IN controller. The 
PU's job is to anticipate and reduce control configuration time, the 
major component of the control latency. Three different on-line 
prediction techniques were tested to learn and predict repetitive 
memory access patterns for three typical parallel processing applications, 
the 2-D relaxation algorithm, matrix multiply and Fast Fourier Transform. 
The predictions were then used by a routing control algorithm to reduce 
control latency by configuring the IN to provide needed memory access 
paths before they were requested. Three prediction techniques were used 
and tested: 1). a Markov predictor, 2). a linear predictor and 3). a 
time delay neural network (TDNN) predictor. As expected, different 
predictors performed best on different applications, however, the TDNN 
produced the best overall results.

Keywords:

On-line Prediction; Learning; Multiprocessors; Memory; Markov Predictor;
Linear Predictor; Time Delay Neural Network

____________________________________________________________________________

The paper is available from:

http://www.neci.nj.nec.com/homepages/giles.html
http://www.neci.nj.nec.com/homepages/sakr.html
http://www.cs.umd.edu/TRs/TR-no-abs.html 

Comments are very welcome.      


--                                 
C. Lee Giles / Computer Sciences / NEC Research Institute / 
4 Independence Way / Princeton, NJ 08540, USA / 609-951-2642 / Fax 2482
www.neci.nj.nec.com/homepages/giles.html
==