From pighizzi@dsi.unimi.it Fri May 27 13:33:55 1994
From: Giovanni Pighizzini <pighizzi@dsi.unimi.it>
Subject: progress report
To: challeng@dimacs.rutgers.edu
Date: Thu, 19 May 1994 17:53:55 +0200 (METDST)
X-Mailer: ELM [version 2.4 PL23]
Content-Type: text
Content-Length: 3251      

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% DIMACS 3rd CHALLENGE                                          %%
%% A practical parallel facility for dynamic programming (latex) %%
%% PROGRESS REPORT
%% D. Bruschi, G. Pighizzini                                     %%
%% Dipartimento di Scienze dell'Informazione                     %%
%% Universita' di Milano                                         %%
%% pighizzi@ghost.dsi.unimi.it                                   %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle[12pt]{article}



\begin{document}
\title{A Practical Parallel Facility for Dynamic Programming}
\author{
Danilo Bruschi  \\
Giovanni Pighizzini \\
{\normalsize Dipartimento di Scienze dell'Informazione}\\
{\normalsize Universit\`{a} degli Studi}\\
{\normalsize Via Comelico 39, 20135 Milano -- ITALY}\\
{\normalsize\tt\{bruschi,pighizzi\}@imiucca.csi.unimi.it}
}
\date{{\em PROGRESS REPORT}}
\maketitle

\section{State of the Art}

Following the suggestions of the Challenge Advisory Board we
are concentrating our efforts on the
development and study of the effects of the application of a parallel
dynamic programming strategy to 
a specific problem
namely the {\em shortest path} problem.
So far we have adapted a dynamic programming strategy to work in parallel 
on the problem just mentioned and
the algorithm obtained
has been implemented
on a CM2 using the C$^*$ language.
Testing and debugging of this code is on progress. The first
benchmarks results are not completely satisfactory thus we are
looking for new parallel techniques for solving shortest path,
in particular we are considering of implementing also the naive
parallel version of Dijkstra's algorithm and the random approximation
scheme proposed by Klein and Sairam (STOC 92).

\smallbreak
As a parallel activity we still continue to work on
the implementation of a
generic routine for
parallel dynamic programming, which we hope to present as a generalization of
the work on the shortest path problem.


\section{Benchmarks}

In agreement with the other group of researchers who is implementing the
shortest path problem (namely Papaefthymiou and Rodrigue at Yale)
we are using for benchmarking our application
random graphs generated by Andrew Goldberg's random graph
generators. Such generators refer but do not use the DIMACS format,
is this a problem?
Papaefthymiou and Rodrigue also suggested of using
Graphs derived from circuits in the MCNC benchmark.
Actually we are exploring also this possibility.

\section{Next Developments}

Since our hardware resources are quite ``weak'' we think of
heavily using the J machine at MIT. We are waiting for the documentation
on this architecture in order to begin the porting of our
application actually running on the CM2,
>from the  C$^*$ of the CM2 to the
message--driven C of the J machine.
Here the main problem will be that
taking advantage of the MIMD nature of the
J-machine which is a message--driven machine,
while the CM2 and C* programming model are data-parallel.
We plan however, with the support of MIT's group, of porting the
application in two or three weeks and then spend the rest of time on
tuning and benchmarking.

\end{document}