臺灣博碩士論文加值系統

對於資料分析而言分類是一種有價值的技術，大部份應用在未管理過的圖樣認定和影像分割，而圖樣的數目很大，因此，設計快速有效平行演算法對於分類要明確十分重要，本論文對 個圖樣和 個中心點，有 個特徵，我們提議有效的演算法在具有可重置匯流排的陣列機上可以有多個處理器，在光纖和電子計算的優勢上，所提議的演算法能夠執行 , , , 和 時間 ，使用 1+ ， 1+ ， ， 1+ 和 1+ 處理器, 對某個常數 ε，ε 1，這個結果分別地改進先前所知的演算法。

Clustering is a valuable technique for data analysis. In most applications such as unsupervised pattern recognition and image segmentation in which the number of patterns may be very large. Therefore, designing fast and processor efficient parallel algorithms for clustering is definitely of fundamental importance. In this paper, for patterns and centers each with features, we propose efficient parallel algorithms for squared error clustering on the arrays with reconfigurable optical buses (AROB) with various number of processors. Based on the advantages of both optical transmission and electronic computation, the proposed algorithms can be run in , , , and time using, 1+ and 1+ , 1+ , 1+ processors, for some constant ε and ε 1, respectively. These results improve the previously known algorithms.

Chapter 1 Introduction …………………………………………………………..1
Chapter 2 The Computation Model……………………………………………...6
Chapter 3 Basic Operations………………………………………………………9
Chapter 4 Definitions and Notations ……………………………………………15
Chapter 5 Parallel Squares Error Clustering Algorithm…………………………18
Chapter 6 Concluding Remarks………………………………………………….25

[1] M. R. Anderberg, { Cluster Analysis for Applications}, Reading, Academic Press, New York, 1973.
[2] Y. Ben-Asher, D. Peleg, R. Ramaswami, and A. Schuster, ''The power of reconfiguration,'' { Journal of Parallel and Distributed Computing}, vol. 13, pp. 139--153, 1991.
[3] D. M. Chiarulli, R. G. Melhem, and S. P. Levitan, ''Using coincident optical pulses for parallel memory addressing,'' {IEEE Computer Mag.}, vol. 20, no. 12, pp. 48--58, 1987.
[4] R. C. Duda and P. E. Hart, { Pattern Classification and Scene Analysis}, Reading, John Wiley and Sons, New York, 1973.
[5] Z. Guo, R. G. Melhem, R. W. Hall, D. M. Chiarulli, and S. P. Levitan, ''Pipelined communications in optically interconnected arrays,'' { Journal of Parallel and Distributed Computing}, vol. 12, no. 3, pp.269--282, 1991.
[6] K. Hwang, H. M. Alnuweiri, V. K. P. Kumar and D. Kim, ''Orthogonal multiprocessor sharing memory with an enhanced mesh for integrated image understanding,'' { CVGIP : Image Understanding, }vol.53, pp. 31-45,1991.
[7] A. Jain and R. Dubes, {m Algorithms for Clustering Data}, Englewood Cliffs, NJ: Prentice-Hall, 1988.
[8] M. Jambu and M. O. Lebeaux, { Cluster Analysis and Data Analysis}, Reading, North-Holland Publishing Company, New York, 1983.
[9] J. F. Jenq and S. Sahni, ''Reconfigurable mesh algorithms for image shrinking, expanding, clustering, and template matching,'' {Proc. of the International Parallel Processing Symposium}, pp. 208-215, 1991.
[10] S. P. Levitan, D. M. Chiarulli, and R. G. Melhem, ''Coincident pulse technique for multiprocessor interconnection structures,'' { Applied Optics}, vol. 29, no. 14, pp. 2024-2033, 1990.
[11] K. Li, Y. Pan and S. Q. Zheng, ''Fast and processor efficient parallel matrix multiplication algorithms on a linear array with a reconfigurable pipelined bus system,'' { IEEE Trans. on Parallel and Distributed systems}, vol. 9, pp. 705-720, 1998.
[12] X. Li and Z. Fang, ''Parallel clustering algorithms,'' { Parallel Computing,} Vol. 11, pp. 275-290, 1989.
[13] R. Miller, V. K. P. Kumar, D. Reisis, and Q. F. Stout, ''Image computations on reconfigurable VLSI arrays,'' { Proc. of IEEE Computer Society Conference on Computer Vision and Pattern Recognition}, pp.925-930, 1988.
[14] L. M. Ni and A. K. Jain, ''A VLSI systolic architecture for pattern clustering,'' {IEEE Trans. on Patt. Analysis. and Machine Intellig.,} vol. PAMI-7, no.1, pp. 79-89, 1985.
[15] Y. Pan and M. Hamdi, ''Quicksort on a linear array with a reconfigurable pipelined bus system,'' { Proc. of the Int. Symposium on Parallel Architectures, Algorithms and Networks}, pp. 313-319, 1996.
[16] Y. Pan and K. Li, ''Linear array with a reconfigurable pipelined bus system--- concepts and applications,''{ Information Sciences -- An International Journal}, vol. 106, no. 3/4, pp. 237-258, 1998.
[17] Y. Pan, K. Li, and S. Q. Zheng, ''Fast nearest neighbor algorithms on a linear array with a reconfigurable pipelined bus system,'' { Parallel Algorithms and Applications}, vol. 13, pp. 1-25, 1998.
[18] S. Pavel and S. G. Akl, ''On the power of arrays with reconfigurable optical bus,'' { Proc. of the Int. Conf. on Parallel and Distributed Processing Techniques and Applications}, pp. 1443-1454, 1996.
[19] S. Pavel and S. G. Akl, ''Matrix operations using arrays with reconfigurable optical buses,'' { Parallel Algorithms and Applications}, vol. 8, pp. 223-242, 1996.
[20] S. Pavel and S. G. Akl, ''Integer sorting and routing in arrays with reconfigurable optical buses,'' { Int. Journal of Foundations of computer science, Special Issue on Interconnection Networks}, vol. 9, no.1, pp. 99-120, 1998.
[21] C. Qiao and R. G. Melhem, ''Time-division communications
in multiprocessor arrays,'' {IEEE Transactions on Computers}, vol. 42,
no. 5, pp. 577-590, 1993.
[22] S. Rajasekaran and S. Sahni, ''Sorting, selection and routing on the arrays with reconfigurable optical buses,'' {IEEE Transactions on Parallel and Distributed Systems}, vol. 8, no. 11, pp.1123-1132, 1997.
[23] S. Ranka and S. Sahni, ''Clustering on a hypercube multicomputer,'' {IEEE Trans. on Parallel and Distributed Systems}, vol.2, no. 2, pp. 129-137, 1991.
[24] H. R. Tsai, S. J. Horng, S. S. Tsai, S. S. Lee, T. W. Kao, and C. H. Chen, ''Parallel clustering algorithms on a reconfigurable arrays of processors with wider bus networks,'' {Proc. of the Int. Conf. On Parallel and Distributed systems}, pp. 630-637, 1997.
[25] B. F. Wang and G. H. Chen, ''Constant time algorithms for transitive closure and some related graph problems on processor arrays with reconfigurable bus systems,'' {IEEE Trans. on Parallel and Distributed Systems}, vol. 1, no. 10, pp. 500-507, 1990.
[26] C. H. Wu, S. J. Horng and H. R. Tsai, ''Template matching on arrays with reconfigurable optical buses'' {Proc. of the Int. Symp. on Operations Research and its Applications}, pp. 127-141, 1998.