文档介绍：Generating Parallel Algorithms for Cluster and
puting?
U. K. Hayashida1, K. Okuda1, J. ta2, and S. W. Song1
1 Universidade de S˜ao Paulo, Brazil,
{ulisses,kunio,song}***@,
/∼song/
2 Instituto Nacional de Pesquisas Espaciais,
Centro de Previs˜ao de Tempo e Estudos Clim´aticos, Brazil
******@
Abstract. We revisit and use the dependence transformation method
to generate parallel algorithms suitable for cluster and puting.
We illustrate this method in two applications: to obtain a systolic matrix
product algorithm, and pute the alignment score of two strings.
The product of two n × n matrices is viewed as multiplying two p × p
matrices whose elements are n/p × n/p submatrices. For m such mul-
tiplications, using p2 processors, the proposed parallel solution gives a
mp3 2
linear speedup of (m+2)p−2 or roughly p . The alignment problem of
two strings of lengths m and n is solved in O(p) communication rounds
and O(mn/p) puting time. We show promising experimental
results obtained on a 16-node Beowulf cluster and on an 18-node grid
called InteGrade, consisting of puters.
1 Introduction
The abundance of low puting resources in clusters and the increasing
network bandwidth make it attractive to run parallel applications with the so-
called grid-puting. We attempt to use efficiently putational
resources that are idle to obtain a