This paper describes an extension of the TNE algorithm, the objective of which is to increase its parallelism and to break the inter-processor deadlocks inherent with the use of TNE. The algorithm, which we call the S...
详细信息
ISBN:
(纸本)9780818671203
This paper describes an extension of the TNE algorithm, the objective of which is to increase its parallelism and to break the inter-processor deadlocks inherent with the use of TNE. The algorithm, which we call the SGTNE algorithm (Semi Global TNE), is executed over a cluster of processors as opposed to TNE, which is executed over a cluster of processes assigned to a single processor. SGTNE helps to break the inter-processor deadlocks by executing a shortest path algorithm over a snapshot of the LPs in a cluster of processors. This paper discusses the algorithm and its implementation and reports on the performance results of simulations of a partitioned fcfs queueing network model executed on the Intel Paragon A4 multiprocessor machine. We also examine the impact of partitioning on the efficient implementation of the SGTNE algorithm. The results obtained indicate that SGTNE yields good speedups and that a partitioning which makes use of a strongly connected component algorithm results in a reduction of 30% in the running time of a simulation when compared to simple partitioning strategies. The results also indicate that SGTNE outperforms TNE.
暂无评论