在過去的30年中，可重組態架構所具有的超高速計算能力，吸引許多研究者與科學家投入該領域，它們是具有強大能力的平行計算模型，但是有些類型的計算問題並沒有被完整地研究清楚，例如：有向圖問題。有方向性的可重組態架構是針對有向圖問題特別開發出來的可重組態架構，這些有方向性的可重組態架構是一種理想化的機器，且只用來處理有向圖問題。在本論文中，我們將嘗試以新的方法並使用無方向性的可重組態架構去處理有向圖問題。
根據我們所知在本研究之前，有二種方法可以在可重組態架構上處理有向圖問題：第一種方法是基於與計算模型無關的矩陣乘法，它被用來解決代數路徑問題，例如遞移閉包、任兩端點間最短路徑、與最小擴張樹等問題，其所使用的計算模型為無方向性的可重組態架構；第二種方法則是使用有方向性的可重組態架構，例如有方向性的可重組態格狀網路、有方向性的可重組態匯流排之處理器陣列，來解決特定的有向圖問題。基於第二種方法的演算法必須利用有方向性的可重組態架構之特定能力才能正確無誤地處理問題，這能力就是它們能夠在匯流排的每一段落控制資料的流向。
在本論文中我們提出第三種解決方案，它是基於那些無方向性的可重組態架構上去解決有向圖問題，例如有向的遞移閉包問題可以在三維n* n* n的可重組態格狀網路用O(log d(D))的時間解決該問題，其中d(D)是有向圖D的直徑，基於有向的遞移閉包演算法的相同設計概念，我們可以解決下列的有向圖問題：強連接圖、強連接元件、環狀圖檢查、樹的建構、任兩端點之最短距離、單源最短距離、直徑、拓樸排序等問題，這些演算法價恰恰證明了這第三種解決方案的威力，因此我們認為這個在無方向性的可重組態架構上有向圖問題解決方案是有相當價值，而這將對超高速計算與即時運算等領域有所貢獻。

Reconfigurable architectures have attracted many researchers and scientists for their high performance computing for the past three decades. They are very powerful parallel computation models, but some types of problems have not been studied completely, for example, the digraph problems. The directional reconfigurable architectures are developed especially for digraph problems, they are idealistic machines for handling such problems. In this dissertation, we focus on digraph problems by using non-directional reconfigurable architectures and try to solve them by a new approach.
Before this study, to our best knowledge, there are two approaches to solve digraph problems on reconfigurable architectures. The first one is on the basis of matrix multiplication which is independent of computation models.
It was used to solve the algebraic path problems (APP), for example, transitive closure (TC), all-pairs shortest path (APSP), the minimum spanning tree (MST), on non-directional reconfigurable architectures. The second approach uses directional reconfigurable architectures, such as directional reconfigurable mesh (DR-Mesh) and complete directional processor arrays with reconfigurable bus systems (CD-PARBS), to solve specified digraph problems. The algorithms of the second approach specifically use the capability of the directional reconfigurable architectures which can control the data flow in each segment of a bus.
In this dissertation, the third approach on non-directional reconfigurable architectures will be proposed to solve many digraph problems. For example, the transitive closure problem can be solved in $O(log \,d(D))$ time on a three-dimensional (3-D) $n\!\times\!n\!\times\!n$ reconfigurable mesh (R-Mesh), where $d(D)$ is the diameter of digraph $D$. Based on the same idea used in the transitive closure algorithm, we can solve the following digraph problems: strongly connected graph, strongly connected component (SCC), cyclic digraph checking, tree construction, all-pairs shortest distance, single source shortest distance, diameter, topological sort (TS). These algorithms show the power of the third approach. So we believe this approach is valuable to digraph problems on non-reconfigurable architectures for the high performance computing and time-critical applications.

[1] Joseph JaJa, An Introduction to Parallel Algorithms, Addison-Wesley, 1992.
[2] G. Estrin, “Organization of computer systems: the fixed plus variable structure computer,” in Proc. Western Joint Computer Conf. 1960, Western Joint Computer Conference.
[3] G. Estrin, “Reconfigurable computer origins: the ucla fixed-plus-variable (f+v) structure computer,” IEEE Ann. Hist. Comput., vol. 24, pp. 3–9, 2002.
[4] Y. Ben-Asher, D. Peleg, R. Ramaswami, and A. Schuster, “The power of reconfiguration,” Lecture Notes in Computer Science, vol. 510, pp. 139–150, 1991.
[5] K. Nakano, “A bibliography of published papers on dynamically reconfigurable architectures,” Parallel Processing Letters, vol. 5, pp. 111–124, 1995.
[6] K. Bondalapati and V. K. Prasanna, “Reconfigurable computing: architectures, models and algorithms,” Current Science, vol. 78, no. 7, pp. 828–837, 2000.
[7] R. Vaidyanathan and J. L. Trahan, Dynamic reconfiguration architectures and algorithms, Kluwer, New York, 2004.
[8] R. Wankar and R. Akerkar, “Reconfigurable architectures and algorithms: A research survey,” International Journal of Computer Science and Applications, vol. 6, no. 1, pp. 108–123, 2009.
[9] R. Miller, V. K. Prasanna, D. Reisis, and Q. F. Stout, “Meshes with reconfigurable buses,” in Processing of 5th MIT Conference on Advanced Research in VLSI, 1988.
[10] R. Miller, V. K. Prasanna, D. Reisis, and Q. F. Stout, “Parallel computations on reconfigurable meshes,” IEEE Transactions on Computers, vol. 42, pp. 678–692, 1993.
[11] B. Pradeep and C. S. R. Murthy, “A constant time algorithm for redundancy elimination in task graphs on processor arrays with reconfigurable bus systems,” Parallel Processing Letters, vol. 3, pp. 171–177, 1993.
[12] C. J. Kuo, C. C. Hsu, and W. C. Fang, “Parallel directed graph algorithms on directional processor arrays with reconfigurable bus systems,” New Generation Computing, vol. 17, pp. 175–200, 1999.
[13] A. A. Bertossi and A. Mei, “Constant time dynamic programming on directed reconfigurable networks,” IEEE Transaction on Parallel and Distributed Systems, vol. 11, pp. 529–536, 2000.
[14] T. T. Pan and S. S. Lin, “Constant-time algorithms for minimum spanning tree problem and related problems on processor arrays with reconfigurable bus systems,” Computer Journal, vol. 45, pp. 174–186, 2002.
[15] S. Warshall, “A theorem on boolean matrices,” Journal of ACM, vol. 9, pp. 11–12, 1962.
[16] R. Tarjan, “Depth-first search and linear graph algorithms,” SIAM Journal on Computing, vol. 1, pp. 146–160, 1972.
[17] A. Aggarwal, R. J. Anderson, and M. Y. Kao, “Parallel depth-first search in general directed graphs,” SIAM Journal on Computing, vol. 19, pp. 397–409, 1990.
[18] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, MIT Press and McGraw-Hill, 1 edition, 1990.
[19] B. F. Wang, G. H. Chen, and F. C. Lin, “Constant time sorting on a processor array with reconfigurable bus system,” Information Processing Letters, vol. 34, pp. 187–192, 1990.
[20] B. F. Wang and G. H. Chen, “Constant time algorithms for transitive closure and some related graph problem on processor arrays with reconfigurable bus systems,” IEEE Transaction on Parallel Distributed System, vol. 1, pp. 500–507, 1990.
[21] M. Y. Kao and P. N. Klein, “Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraph,” in Proc. of 22nd ACM Symposium on Theory of Computing, 1990.
[22] G. H. Chen, B. F.Wang, and C. J. Lu, “On the parallel computation for the algebraic path problem,” IEEE Transaction on Parallel Distributed Systems, vol. 3, pp. 251–256, 1992.
[23] Y. Han, V. Pan, , and J. Reif, “Efficient parallel algorithm for computing all pair shortest paths in directed graphs,” in Proc. 4th ACM symp. on Parallel Algorithms and Architectures, 1992.
[24] M. Y. Kao, “Linear-processor nc algorithm for planar directed graphs i: strongly connected components,” SIAM Journal on Computing, vol. 22, pp. 431–459, 1993.
[25] E. Cohen, “Efficient parallel shortest-path in digraph with a separator decomposition,” in Proc. 5th ACM Symp. On Parallel Algorithms and Architectues (SPAA’93), 1993, pp. 57–67.
[26] P. Thangavel and V. P. Muthuswamy, “Parallel algorithms for addition and multiplication on processor arrays with reconfigurable bus systems,” Information Processing Letters, vol. 46, pp. 89–94, 1993.
[27] G. H. Chen and B. F. Wang, “Sorting and computing convex hulls on processor arrays with reconfigurable bus systems,” Information Science, vol. 72, pp. 191–206, 1993.
[28] R. Vaidyanathan and J. L. Trahan, “Optimal simulation of multidimensional reconfigurable meshes by two dimensional reconfigurable meshes,” Information Processing Letters, vol. 47, pp. 267–273, 1993.
[29] S. S. Lin, “Cost-effective algorithms for processor arrays with reconfigurable bus systems,” Journal of the Chinese Institute of Engineers, vol. 17, no. 2, pp. 279–288,
1994.
[30] M. Nigam and S. Sahni, “Sorting n number on n *n reconfigurable meshes with buses,” Journal of Parallel and Distributed Computing, vol. 23, pp. 37–48, 1994.
[31] Y. C. Chen andW. T. Chen, “Constant time sorting on reconfigurable meshes,” IEEE Transaction on Computers, vol. 43, no. 6, pp. 749–751, 1994.
[32] J. W. Jang and V. K. Prasanna, “An optimal sorting algorithm on reconfigurable mesh,” Journal of Parallel and Distributed Computing, vol. 25, pp. 31–41, 1995.
[33] G. H. Chen, S. Olariu, J. L. Schwing, B. F. Wang, and J. Zhang, “Constant time tree algorithms on reconfigurable meshes on size n* n,” Journal of Parallel and Distributed Computing, vol. 26, pp. 137–150, 1995.
[34] T. Hayashi, K. Nakano, and S. Olariu, “Efficient list ranking on the reconfigurable mesh with applications,” Tech. Rep., Hayashi Laboratory Technical Report TR96-03, 1996.
[35] T. H. Lai and M. J. Sheng, “Constructing euclidean minimum spanning tree and all nearest neighbors on reconfigurable meshes,” IEEE Transaction on Parallel Distributed Systems, vol. 7, pp. 806–817, 1996.
[36] J. L. Trahan, R. Vaidyanathan, and C. P. Subbaraman, “Constant time graph algorithms on the reconfigurable multiple bus machine,” Journal of Parallel and Distributed
Computing, vol. 46, pp. 1–14, 1997.
[37] H. R. Tsai, S. J. Horng, S. S. Tsai, T. W. Kao, and S. S. Lee, “Solving an algebraic path problem and some related graph problems on a hyper-bus broadcast network,” IEEE Transaction on Parallel Distributed Systems, vol. 8, pp. 1226–1235, 1997.
[38] H. R. Tsai, S. J. Horng, S. S. Lee, S. S. Tsai, and T. W. Kao, “Parallel hierarchical clustering algorithms on processor arrays with a reconfigurable bus system,” Pattern
Recognition, vol. 30, pp. 801–815, 1997.
[39] J. Jang, M. Nigam, V. K. Prasanna, and S. Sahni, “Constant time algorithms for computational geometry on the reconfigurable mesh,” IEEE Transaction on Parallel and Distributed Systems, vol. 8, no. 1, pp. 1–12, 1997.
[40] J. Jang, H. Park, and V. K. Prasanna, “An optimal multiplication algorithm on reconfigurable mesh,” IEEE Transaction on Parallel and Distributed Systems, vol. 8,
pp. 521–532, 1997.
[41] B. Dixon and R. E. Tarjan, “Optimal parallel verification of minimum spanning trees in logarithmic time,” Algorithmica, vol. 17, no. 1, pp. 11–18, 1993.
[42] C. H.Wu, S. J. Horng, and H. R. Tsai, “Efficient parallel algorithms for hierarchical clustering on arrays with reconfigurable optical buses,” Journal of Parallel and Distributed Computing, vol. 60, pp. 1137–1153, 2000.
[43] Y. Wan, Y. Xu, X. Gu, and G. Chen, “Efficient minimum spanning tree algorithms on the reconfigurable mesh,” Journal of Computer Science and Technology, vol. 15, pp. 116–125, 2000.
[44] 潘典台, 可重組態匯流排之處理器陣列上之常數時間最小擴張樹演算法, 國立臺灣師範大學資訊教育研究所碩士論文, 1998.
[45] K. W. Chong, Y. Han, Y. Igarashi, and T. W. Lam, “Improving the efficiency of parallel minimum spanning tree algorithms,” Discrete Applied Mathematics, vol. 126, pp. 33–54, 2003.
[46] W. Schudy, “Finding strongly connected components in parallel using o(log^2 n) reachability queries,” in Proceedings of the twentieth annual symposium on Parallelism in algorithms and architectures, 2008.
[47] J. H. Reif, “Depth-first search is inherently sequential,” Information Processing Letters, vol. 20, pp. 229–234, 1985.
[48] V. L. Jan, Ed., Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, USA, 1990.