voula@utcsri.UUCP (Voula Vanneli) (02/27/85)
FLASH ANNOUNCEMENT
UNIVERSITY OF TORONTO
DEPARTMENT OF COMPUTER SCIENCE
THEORETICAL ASPECTS SEMINAR - Friday, March 1, 11 a.m., RS
211,
(_R_S = _R_o_s_e_b_r_u_g_h _B_u_i_l_d_i_n_g, _T_a_d_d_l_e_c_r_e_e_k _R_o_a_d)
Peter H. Hochschild
Stanford University
"Construction of Resource-Efficient Parallel Algorithms"*
Abstract
This talk concerns the problem of exploiting the possi-
bilities of parallel computation inherent in VLSI. We have
developed several paradigms for the construction of effi-
cient parallel algorithms. These paradigms are effective in
designing algorithms for solving a variety of combinatorial
and pattern-matching problems. The resulting space- and
time-efficient programs operate on simple and regular paral-
lel architectures that are suitable for VLSI implementation.
Many of our algorithms owe their efficiency to _f_i_l_t_r_a_-
_t_i_o_n. A filter is a device used to rapidly discard
irrelevant input data. This mechanism can reduce the
storage, time, and communication requirements of a wide
variety of problems. Filter construction demands balancing
two opposing goals. On the one hand, a filter must operate
quickly enough to avoid becoming a bottleneck. On the other
hand, it must be thorough enough to discard a significant
portion of the data. Thus, in general, a filter performs a
kind of approximation to the desired computation. This
approximation is later refined to yield the correct result.