UW Theory Seminar. Dr. Fich on "New Bounds for Parallel Prefix Curcuits"
watmath!mwang
_D_E_P_A_R_T_M_E_N_T _O_F _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E
_U_N_I_V_E_R_S_I_T_Y _O_F _W_A_T_E_R_L_O_O
_S_E_M_I_N_A_R _A_C_T_I_V_I_T_I_E_S
_T_H_E_O_R_Y _S_E_M_I_N_A_R - Monday, February 14, 1983.
Dr. Faith E. Fich of University of California, Berkeley,
will speak on ``_N_e_w _B_o_u_n_d_s _f_o_r _P_a_r_a_l_l_e_l _P_r_e_f_i_x _C_i_r_c_u_i_t_s.''
TIME: 3:30 PM
ROOM: M&C 3008 (Please Note)
_A_B_S_T_R_A_C_T
Parallel prefix circuits are combinational circuits that
take $ n $ inputs
x sub 1 , x sub 2 , ..., x sub n and produce the n
outputs
x sub 1 , x sub 1 o x sub 2 , ..., x sub 1 o ... o x
sub n , where $ oo $ is an arbitrary associative binary
operation that can be performed by a gate. Among other
applications, these circuits have been used to construct
fast adders and to convert sequential circuits into paral-
lel ones.
Structural information is obtained concerning parallel
prefix circuits in which the number of inputs is a power
of two and the depth is the minimum possible. This infor-
mation leads to lower bounds for the number of gates in
these circuits. A new, near-optimal construction for
parallel prefix circuits will also be described.
February 8, 1983
