臺灣博碩士論文加值系統

前置運算就是對n個輸入數值x1, x2,..., xn與具結合性
的二元運算,求得n個前置值x1, x2,..., xi,1≦i≦n.因為
前置運算有很多應用,所以有許多的前置電路被設計出來.任何一個前置電路
D,其深度d(D)與運算節點數s(D)滿足d(D)+s(D)≧2n-2.因此,若d(D)
+s(D)=2n-2,則D為最佳前置電路.前置電路的運算節點個數愈少,則所需
的積體電路面積就愈小;深度愈小,則輸出的速度愈快;節點的扇出愈大,則所需
的積體電路面積會愈大,速度也愈慢.在本論文中,我們建造扇出為4的最佳前置電路WE4.
且深度介於2log n-6與2log n-3之間.在深度的比較上,WE4與扇出為4的最佳前置電路Z4各有小部分比對方多一,
但在大部分的情況,d(WE4)=d(Z4);與已知的其他扇出為4的最佳前置電路相比,WE4的深度是最小的.
由於WE4的扇出比無限扇出的最佳前置電路QL的扇出小得多,所以WE4的積體電路面積較小,
速度也可能比QL快.

Give n values x1, x2,..., xn and an associative binary operation , the prefix
problem is to computex1, x2,..., xi,1≦i≦n.　Because prefix computation has
many applications, many combinational circuits for solving the prefix problem, called prefix
circuit, has been designed.　The depth d(D) and the size s(D) of an n-input prefix circuit
D satisfy d(D) + s(D) ≧2n - 2; thus, the prefix circuit is depth-size optimal if d(D) +
s(D) = 2n - 2. A prefix circuit with a smaller size requires less VLSI area, and one with
smaller depth is faster. In addition, a node with a greater fan-out is slower and requires
larger VLSI area. In this thesis, we construct a depth-size optimal parallel prefix circuit WE4 with
fan-out 4, the depth of WE4 between 2log n-6 and 2log n-3.Compared with another depth-
size optimal prefix circuit Z4, the depth of WE4 may be less than or greater than that of
Z4. The depth of WE4 is smaller than all the other known prefix circuits with fan-out 4.　
Compared with QL, a depth-size optimal prefix circuit with unbounded fan-out, WE4 may
have may a greater or equal depth than QL; however, because the fan-out of WE4 is smaller than
that of QL, the VLSI area of WE4 is smaller, and WE$ may be faster.

第 1 章　　　簡介　　　　　　　　　　　　　　　　　　　　　1
　1.1. 平行前置電路的介紹　　　　　　　　　　1
　1.2. 相關研究　　　　　　　　　　　　　　　　　　　　3
　1.3. 論文組織　　　　　　　　　　　　　　　　　　　　4
第 2 章　　　舊有的前置電路及性質　　　　　　　　　　　　　5
　2.1. 分層式前置電路P 　　5
　2.2. 扇出最多為4的前置電路Q　　 　　　　　　　　　　 6
　2.3. 節點數最佳前置電路W 　　　　　　　　　　　 8
　2.4. 前置電路的合成及節點數最佳前置電路的相關性質　　8
　2.5. 最佳前置電路Z4及QL的深度 　 10
第 3 章　　　扇出為4的最佳前置電路 　　　　　　　　　　　 11
　3.1. 扇出為4的節點數最佳前置電路WL 　　　　　　　11
　3.2. 節點數最佳前置電路WV　 　　　　　　　　 16
　3.3. 扇出為4的最佳前置電路WE4 　　　 　　　　　 21
第 4 章　　　最佳前置電路的比較　　　　　　　　　　　　　 27
第 5 章　　　結論與未來研究方向　　　　　　　　　　　　　 31
　5.1. 結論 　　　　　　　　　　　　　　　　　 31
　5.2. 未來研究方向　　　　　　　　　　　　　　　　　 31
參考資料　　　　

[1] S.G. Akl, Parallel Computation: Models and Methods.　　Upper Saddle River,
NJ: Prentice-Hall, 1997.
[2] R.P. Brent and H.T. Kung, "A regular layout for parallel adders," IEEE
Trans. Comput., vol. C-31, pp. 260-264, Mar. 1982.
[3] D.A. Carlson and B. Sugla, "Limited width parallel prefix circuits," J.
Supercomput., vol. 4, pp. 107-129, June 1990.
[4] 陳健男, 建造深度與節點數最佳的平行前置電路Z4, Master Thesis, Dept. of
Electronic Engineering, National Taiwan University of Science and Technology,
Taipei, 2001.
[5] 陳健男, 扇出為4的成本最佳的平行前置電路Z4, Master Thesis, Dept. of
Electronic Engineering, National Taiwan University of Science and Technology,
Taipei, 2001.
[6] R. Cole and U. Vishkin, "Faster optimal parallel prefix sums and list
ranking," Infom. Contr., vol. 81, pp. 334-352, 1989.
[7] F.E. Fich, "New bounds for parallel prefix circuits," in Proc. 15th Symp.
on the Theory of Computing, 1983, pp. 100-109.
[8] Y.-H. Hsu, Design and layout of depth-size optimal parallel prefix circuits, Master
Thesis, Institute of computer Science and Information Engineering, National Taiwan
University of Science and Technology, Taipei, 2000.
[9] C.P. Kruskal, T. Madej, and L. Rudolph, "Parallel prefix on fully
connected direct connection machines," in Proc. Int. Conf. on Parallel
Processing, 1986, pp. 278-284.
[10] R.E. Ladner and M.J. Fischer, "Parallel prefix computation," J. ACM, vol.
27, pp. 831-838, Oct. 1980.
[11] S. Lakshmivarahan and S.K. Dhall, Parallel Computing Using the Prefix
Problem.　　Oxford, UK: Oxford University Press, 1994.
[12] S. Lakshmivarahan, C.M. Yang, and S.K. Dhall, "On a new class of optimal
parallel prefix circuits with (size + depth) = 2n-2 and log n≦ depth ≦　(
2log n-3)," in Proc. 1987 Int. Conf. on Parallel Processing, 1987, pp. 58-
65.
[13] Y.-C. Lin, "Optimal parallel prefix circuits with fan-out 2 and
corresponding parallel algorithms," Neural, Parallel & Scientific Computations,
vol. 7, pp. 33-42, Mar. 1999.
[14] Y.-C. Lin, Y.-H. Hsu,and C.-K. Liu "depth-size optimal parallel prefix circuits with
fan-out 4 and small depth," in Proc. 2nd IASTED Int. Conf. on Parallel and Distributed
Computing, Application ,and Techniques, 2001.
[15] Y.-C. Lin and C.M. Lin, "Efficient parallel prefix algorithms on
multicomputers," J. Information Science Engineering, vol. 16, pp. 41-64, Jan. 2000.
[16] Y.-C. Lin and C.-K. Liu, " Constructing optimal parallel prefix circuits," in Proc.
1999 National Computer Symp., 1999, pp. C-313-320.
[17] Y.-C. Lin and C.-K. Liu, "Finding optimal parallel prefix circuits with
fan-out 2 in constant time," Inform. Process. Lett., vol. 70, pp. 191-195, May 1999.
[18] Y.-C. Lin and C.-C. Shih, "Optimal parallel prefix circuits with fan-out
at most 4," in Proc. 2nd IASTED Int. Conf. on Parallel and Distributed
Computing and Networks, 1998, pp. 312-317.
[19] Y.-C. Lin and C.-C. Shih, "A new class of depth-size optimal parallel
prefix circuits," J. Supercomput., vol. 14, pp. 39-52, July 1999.
[20] Y.-C. Lin and C.-S. Yeh, "Efficient parallel prefix algorithms on
multiport message-passing systems," Inform. Process. Lett., vol. 71, pp. 91-
95, July 1999.
[21] C.-K. Liu, Depth-size optimal parallel prefix circuits with small Depth, Master
Thesis, Institute of computer Science and Information Engineering, National Taiwan
University of Science and Technology, Taipei, 2000.
[22] M.J. Quinn, parallel computing: Theoty and Paractice. New York: McGraw-Hill, 1994.
[23] 施朝正, 建造一些深度與節點數最佳的平行前置電路, Ph.D. Thesis, Dept. of
Electronic Engineering, National Taiwan University of Science and Technology,
Taipei, 2001.
[24] M. Snir, "Depth-size trade-offs for parallel prefix computation," J.
Algorithms, vol. 7, pp. 185-201, 1986.
[25] H. Wang, A. Nicolau, and K.S. Siu, "The strict time lower bound and
optimal schedules for parallel prefix with resource constraints," IEEE Trans.
Comput., vol. 45, pp. 1257-1271, Nov. 1996.
[26] N.H.E. Weste and K. Eshraghian, Principles of CMOS VLSI Design: A System
Perspective.　2nd ed.　 Reading, MA: Addison-Wesley, 1993.