A Combinatorial Problem Related to Multimodule Memory Organizations

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Combinatorial Problem Related to Multimodule Memory Organizations

Full text

Pdf (610 KB)

Source

Journal of the ACM (JACM) archive
Volume 21 , Issue 3 (July 1974) table of contents

Pages: 392 - 402

Year of Publication: 1974

ISSN:0004-5411

Authors

C. K. Wong	IBM Thomas J. Watson Research Center, P.O. Box 218, Yorktown Heights, NY and University of Illinois, Urbana, Illinois
Don Coppersmith	Department of Mathematics, Harvard University, Science Center, One Oxford Street, Cambridege, MA and IBM Thomas J. Watson Research Center, Yorktown Heights, New York

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 34, Citation Count: 19

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321832.321838 What is a DOI?

ABSTRACT

This paper deals with a combinatorial minimization problem arising from studies on multimodule memory organizations. Instead of searching for an optimum solution, a particular solution is proposed and it is demonstrated that it is close to optimum. Lower bounds for the objective functions are obtained and compared with the corresponding values of the particular solution. The maximum percentage deviation of this solution from optimum is also established.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BARNES, G. H., ET AL. The Illiac IV computer. 1EEE Trans. C-17, 8 (1968), 746-757.
	2	M. R. Garey , R. L. Graham , J. D. Ullman, Worst-case analysis of memory allocation algorithms, Proceedings of the fourth annual ACM symposium on Theory of computing, p.143-150, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804907]
	3	GRAHAM, R.L. Bounds on multiprocessing anomalies and related pa~king algorithms. Pro c. AFIPS 1972 SJCC, pp. 205-218.
	4	David S. Johnson, Approximation algorithms for combinatorial problems, Proceedings of the fifth annual ACM symposium on Theory of computing, p.38-49, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804034]
	5	LIu, C. L. Introduction to Combinatorial Mathematics. McGraw-Hill, New York, 1968.
	6	LIU, C. L. Optimal scheduling on multi-processor computing systems. Proc. 13th Annual Symposium on Switching and Automata Theory, 1972, pp. 155--160.
	7	N~SVSRGELT, J., AND Wor~(~, C.K. On binary search trees. Proc. IFIP Cong. 1971, North- Holland Pub. Co., Amsterdam, 1972, pp. 91-98.
	8	Sa~ON~, H. S. The organization of high-speed memory ~or parallel block transfer of data, IEEE Trans. C-19, 1 (1970), 47-53.
	9	C. K. Wong , C. L. Liu , J. Apter, A drum scheduling algorithm, 1. Fachtagung über Automatentheorie und Formale Sprachen, p.267-275, July 09-12, 1973
	10	WONG, C. K., AND MxI)VOCKS, T.W. A generalized Pascal's triangle. Fibonacci Quart. (to appear).

CITED BY 19

	F. K. Hwang, A survey on multi-loop networks, Theoretical Computer Science, v.299 n.1-3, p.107-121, 18 April 2003
	L. Narayanan , J. Opatrny , D. Sotteau, All-to-all optical routing in optimal chordal rings of degree four, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.695-703, January 17-19, 1999, Baltimore, Maryland, United States
	Behrooz Parhami , Ding-Ming Kwai, Periodically Regular Chordal Rings, IEEE Transactions on Parallel and Distributed Systems, v.10 n.6, p.658-672, June 1999
	Robin Chi-Feng Chan , Chiuyuan Chen , Zhi-Xin Hong, A simple algorithm to find the steps of double-loop networks, Discrete Applied Mathematics, v.121 n.1-3, p.61-72, 15 September 2002
	D H. Lawrie , A H. Sameh, The computation and communication complexity of a parallel banded system solver, ACM Transactions on Mathematical Software (TOMS), v.10 n.2, p.185-195, June 1984
	Chiuyuan Chen , F. K. Hwang, The Minimum Distance Diagram of Double-Loop Networks, IEEE Transactions on Computers, v.49 n.9, p.977-979, September 2000
	Lali Barrière, Symmetry properties of chordal rings of degree 3, Discrete Applied Mathematics, v.129 n.2-3, p.211-232, 01 August 2003
	Tomaž Dobravec , Borut Robič , Janez Žerovnik, Permutation routing in double-loop networks: design and empirical evaluation, Journal of Systems Architecture: the EUROMICRO Journal, v.48 n.13-15, p.387-402, May 2003
	F. K. Hwang, A complementary survey on double-loop networks, Theoretical Computer Science, v.263 n.1-2, p.211-229, July 28 2001
	F. Aguiló , D. Arteaga , I. Diego, A symbolical algorithm on additive basis and double-loop networks, Theoretical Computer Science, v.319 n.1-3, p.423-439, June 10, 2004
	Krishnendu Mukhopadhyaya , Bhabani P. Sinha, Fault-Tolerant Routing in Distributed Loop Networks, IEEE Transactions on Computers, v.44 n.12, p.1452-1456, December 1995
	Chiuyuan Chen , F. K. Hwang , J. S. Lee , S. J. Shih, The existence of hyper-L triple-loop networks, Discrete Mathematics, v.268 n.1-3, p.287-291, 06 July 2003
	L. M. Huisman , S. Kundu, Highly Reliable Symmetric Networks, IEEE Transactions on Parallel and Distributed Systems, v.5 n.1, p.94-97, January 1994
	Domingo Gómez , Jaime Gutierrez , Álvar Ibeas, Optimal routing in double loop networks, Theoretical Computer Science, v.381 n.1-3, p.68-85, August, 2007
	Carmen Martínez , Enrique Vallejo , Ramón Beivide , Cruz Izu , Miquel Moretó, Dense Gaussian networks: suitable topologies for on-chip multiprocessors, International Journal of Parallel Programming, v.34 n.3, p.193-211, June 2006
	Chiuyuan Chen , James K. Lan , Wen-Shiang Tang, An efficient algorithm to find a double-loop network that realizes a given L-shape, Theoretical Computer Science, v.359 n.1, p.69-76, 14 August 2006
	Valentin Brimkov, Algorithmic and explicit determination of the Lovász number for certain circulant graphs, Discrete Applied Mathematics, v.155 n.14, p.1812-1825, September, 2007
	Jinn-Shyong Yang , Jou-Ming Chang , Shyue-Ming Tang , Yue-Li Wang, Reducing the Height of Independent Spanning Trees in Chordal Rings, IEEE Transactions on Parallel and Distributed Systems, v.18 n.5, p.644-657, May 2007
	James K. Lan , Victor W. Liu , Chiuyuan Chen, Improved upper and lower bounds on the optimization of mixed chordal ring networks, Information Processing Letters, v.109 n.13, p.757-762, June, 2009