[ont.events] UW Theory Seminar. Dr. Fich on "New Bounds for Parallel Prefix Curcuits"

mwang (02/08/83)

     _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