\input zb-basic
\input zb-ioport
\iteman{io-port 04143412}
\itemau{Barnard, D.T.; Skillicorn, D.B.}
\itemti{Pipelining tree-structured algorithms on SIMD architectures.}
\itemso{Inf. Process. Lett. 35, No.2, 79-84 (1990).}
\itemab
Summary: There are many algorithms that are tree-structured and that are usually implemented on systolic arrays or other kinds of custom hardware. Implementing them on other highly parallel architectures can be very inefficient because the number of processors in use falls very quickly. We present a method of pipelining such algorithms on SIMD architectures for which processor utilization is asymptotically optimal. We also show how consideration of ability to be pipelined enables classification of algorithm complexity within the classes $NC\sp 1$ and $NC\sp 2$.
\itemrv{~}
\itemcc{}
\itemut{SIMD architectures; pipelined architectures; processor allocation; divide-and-conquer; parallel algorithms; CRCW PRAM; algorithm complexity}
\itemli{doi:10.1016/0020-0190(90)90110-J}
\end