建造平行的最佳前置電路

Abstract

前置運算是對n 個輸值x1, x2,..., xn 與具結合性的二元運算⊗，求得n 個前置值x1 ⊗ x2 ⊗...⊗ xi，1≦i≦n。由於前置計算的應用很廣泛，所以已有許多前置運算的電路被設計出來。任一前置電路D(n)的深度d(D(n))與運算節點數s(D(n))滿足d(D(n))+s(D(n))≧2n-2。若d(D(n))+s(D(n))=2n-2，則稱D(n)W(n)為深度-節點數最佳的前置電路。前置電的運算點數愈小，則所需的積體電路面積就愈小；深度愈小，則輸出的速度愈快。而節點的扇出愈小，則所需的積體電路面積會愈小，速度也愈快。在本論文中，我們導出一個運算節點數的下限，並且建造出節點數最要的平行前置電路W(n)。這個電路被用於建造兩個深度-節點數最佳的平行前置電路M(n)及M4(n)。其中M(n)具無限扇出，而M4(n)的扇出為4。在大部分的情況下，M(n)的深度不會比以前的前置電路之深度大。雖然d(M4(n))≧d(M(n))，由於M4(n)的扇出比M(n)的小，因此M4(n)所需的積體電路面積會較小，而且M4(n)的速度可能不遜於M(n)。