具有方向性的可重組態格狀網路(Directed Reconfigurable Mesh，簡稱DRM)為一種平行處理的計算模型，一個三維具有方向性的DRM包含一個nxnxn處理器的立體形陣列和一個可重組態的匯流排系統。在此三維的DRM模型中，每個處理器都有六個方向的通訊埠，每個方向的通訊埠有輸入資料的輸入埠(input port)和輸出資料的輸出埠(output port)。我們可以任意動態重組所有處理器的組態，進而將處理器陣列切割成數個不同的獨立子網路，在子網路中我們可以做快速的資料傳輸與計算，於是便有研究者藉由這個平行模型，發展出更有效率或常數時間的平行演算法，以解決許多具有平行性和方向性的複雜問題。
在本篇論文中，我們首先提出了一個嶄新的、針對有向圖形上的遞移包矩陣演算法。我們的演算法可以在O(1)時間內利用O(nxnxn)個處理器在三維的DRM模型上完成計算。此外，再藉由這個常數時間遞移包矩陣演算法以及有向圖的特性，我們可以解決其他有向圖形上的問題，包括有向圖的緊密連通測試、尋找緊密連通元件、拓撲排序、以及無迴圈有向圖的單一端點最短單位路徑，這些問題均可在O(1)時間內，利用O(nxnxn)個處理器在三維的DRM模型上完成演算法的計算。

A directed reconfigurable mesh(abbreviated to DRM) is a parallel computation model, which consists of a 3-dimensional array with n^3 processors and a reconfigurable bus system. In this 3-D model, each processor has six direction’s switches and there is one input port and one output port for each direction. We can dynamically setup the configurations of all processors in order to form different and independent sub-buses in the processor array. In each sub-buses the data can be broadcasted in fixed units of time. There are a lot of researchers that develop efficient or constant-time algorithms based on this parallel computation model in order to solve many complicated problems.
In this thesis, we propose a new O(1)-time algorithm for computing the transitive closure of digraph. Our algorithm is designed on a 3-dimensional nxnxn DRM, where n is the number of vertices in the graph. Using the O(1)-time transitive closure algorithms and the properties of digraph, we are able to develop many other related digraph algorithms that take O(1) time on a 3-dimensional nxnxn DRM. These problems include strongly connected component testing, finding the strongly connected component, topological sort, and the single source shortest path of acyclic digraph.

【1】Ben-Asher, Y., Peleg, D., Ramaswami, R. and Schuster, A., “The Power of Reconfiguration,” Journal of Parallel and Distributed Computing, Vol. 13, pp. 139-153(1991).
【2】Bertossi, A. A. and Mei, A., “Constant Time Dynamic Programming on Directed Reconfigurable Networks,” IEEE Transactions on Parallel and Distributed Systems. Vol. 11, No. 6, pp. 529-536(July 2000).
【3】Chen, D. Z. and Lee, D. T., “Solving the All-Pair Shortest Path Problem on Interval and Circular-Arc Graphs,” Parallel Processing Symposium, 1994. Proceedings., Eighth International, pp.224 –228(1994).
【4】Chen, G. H., Wang, B. F. and Lu, C. J., “On the Parallel Computation of the Algebraic Path Problem,” IEEE Transactions on Parallel and Distributed Systems, Vol. 3, No. 2, pp. 251-256(1992).
【5】Cormen, T. H., Leiserson, C. E., Rivest, R. L., Introduction to Algorithm, McGraw-Hill Book Company, 1998.
【6】Das, S. K. and Deo, N., “Divide-and-Conquer-Based Optimal Parallel Algorithms for Some Graph Problems on EREW PRAM Model,” IEEE Transactions on circuits and systems. Vol. 35, no. 3, pp. 312-322(March 1988).
【7】Dey, S. and Srimani, P. K., “Fast Parallel Algorithm for All-Pairs Shortest Path Problem and its VLSI implementation,” IEE proceedings, Vol. 136, Pt. E, No. 2, pp. 85-89(1989).
【8】Ercal, F. and Lee. H. C., “Time-Efficient Maze Routing Algorithms on Reconfigurable Mesh Architectures,” Journal of Parallel and Distributed Computing, Vol. 44, pp. 133-140(1997).
【9】Hsieh, C. L., and Lin, S. S., “The Designs and Analyses of Parallel Algorithms for Some Problems on Special Graphs,” Master Thesis, The National Taiwan Normal University, Taiwan, R.O.C. (1999).
【10】Ibarra. O. H. and Zheng, Q., “On the Shortest Path Problem for Permutation Graphs, “ Parallel Processing Symposium, 1993., Proceeding of Severnth International, 1993, pp. 198-204(1993).
【11】Jang, J. and Prasanna, V. K., “An Optimal Sorting Algorithm on Reconfigurable Mesh,” Parallel Processing Symposium, 1992. Proceedings., Sixth International, pp. 130 –137(1992).
【12】Li, H. and Maresca, M, “Polymorphic-Torus Network,” IEEE Transactions on Computers, Vol. 38, No. 9, pp. 1345-1351(September 1989).
【13】Li, J, Pan, Y. and Shen, H., “More Efficient Topological Sort Using Reconfigurable Optical Buses,” The 2nd International Conference on Parallel and Distributed Computing, Applications, and Technologies, July 9-11, 2001, Taipei, Taiwan.
【14】Li, K., Pan, Y. and Hamdi, M., “Solving graph theory problems using reconfigurable pipelined optical buses,“ Parallel Computing, Vol. 26, No. 6, pp. 723-735(May 2000).
【15】Ma, J., Iwama, K., Takaoka, T. and Gu, Q. P., “Efficient Parallel and Distributed Topological Sort Algorithms,” Parallel Algorithms/Architecture Synthesis, 1997. Proceedings., Second Aizu International Symposium, pp. 378 –383(1997).
【16】Maresca, M., “Polymorphic Processor Arrays,” IEEE Transactions on Parallel and Distributed Systems, Vol. 4, No. 5, pp. 490-506(May 1993).
【17】Mazumder, P., “Parallel VLSI-routing Models for Polymorphic Processors Array, “ 10th International Conference on VLSI Design, pp. 10-14(January 1997).
【18】Miller, R. Prasanna-Kumar, V. K., Reisis, D. I. And Stout, Q. F., “Parallel Computations on Reconfigurable Meshes,” IEEE Transactions on Computers, Vol. 42, No. 6, pp. 678-692(June 1993).
【19】Mulmuley, K. and Shah, P., “A Lower Bound for the Shortest Path Problem,” Computational Complexity, 2000. Proceedings. 15th Annual IEEE Conference on 2000, pp. 14-21(2000).
【20】Narayanan, P. J., “Single Source Shortest Path Problem on Processor Arrays,” Frontiers of Massively Parallel Computation, 1992., Fourth Symposium on the 1992, pp. 553-556(1992).
【21】Nigram, M. and Sahni, S., “Sorting n numbers on n ´ n Reconfigurable Meshes with Buses,” Journal of Parallel and Distributed Computing 23, pp. 37-48(1994).
【22】O’Hallaron, D. R., “Uniform Approach for Solving Some Classical Problems on a Linear Array,” IEEE Transactions on Parallel and Distributed Systems, Vol. 2, No. 2, pp. 236-241(April 1991).
【23】Olariu, S., Schwing, J. L. and Zhang, J., “Integer Sorting in O(1) Time on an n´n Reconfigurable Mesh,” Computers and Communications, 1992. Conference Proceedings., Eleventh Annual International Phoenix Conference, pp. 480 –484(1992).
【24】Olariu, S., Schwing, J. L. and Zhang, J., “Fundamental Data Movement Algorithms for Reconfigurable Meshes,” Computers and Communications, 1992. Conference Proceedings, Eleventh Annual International Phoenix Conference on, 1992. pp. 472-479(1992).
【25】Olariu, S., Schwing, J. L. and Zhang, J., “Interval-Related Problems on Reconfigurable Meshes,”, Application Specific Array Processors, 1992. Proceedings of the International Conference on , 1992 , pp. 445 –455(1992).
【26】Pan. T. T., and Lin, S. S., “Constant-Time Algorithms for Minimum Spanning Tree Problem on Processor Arrays with Reconfigurable Bus System,” Master Thesis, The National Taiwan Normal University, Taiwan, R.O.C. (1998).
【27】Thorup, M., “Undirected Single Source Shortest Paths in Linear Time,” Foundations of Computer Science, 1997. Proceedings. 38th Annual Symposium on, 1997, pp. 12-21(1997).
【28】Trahan, J. L., Vaidyanathan, R., and Subbaraman, C. P., “Constant Time Graph Algorithms on the Reconfigurable Multiple Bus Machine,” Journal of Parallel and Distributed Computing. Vol. 46, pp. 1-14(1997).
【29】Tsai, H. R., Horng, S. J., Tsai, S. S., Kao, T. W. and Lee, S. S., “Solving An Algebraic Path Problem and Some Related Graph Problems on a Hyper-Bus Broadcast Network,” IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 12, pp. 1226-1235(December 1997).
【30】Wang, B. F., and Chen, G.. H., “Constant Time Algorithms for the Transitive Clousure and Some Related Graph Problems on Processor Arrays with Reconfigurable Bus System,” IEEE Transactions on Parallel and Distributed Systems. Vol. 1, No. 4, pp. 500-507(1990).
【31】Y. D. Lai and S. S. Lin, “The Design and Analyses of Parallel Algorithms for Some Problems on Permutation and Interval Graphs,” Master Thesis, The National Taiwan Normal University, Taiwan, R.O.C. (2000).