Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!mips!news.cs.indiana.edu!rutgers!rochester!pt.cs.cmu.edu!gandalf.cs.cmu.edu!lindsay
From: lindsay@gandalf.cs.cmu.edu (Donald Lindsay)
Newsgroups: comp.arch
Subject: Re: Networking for Distributed Computing
Keywords: Kung's Law
Message-ID: <12733@pt.cs.cmu.edu>
Date: 21 Apr 91 00:47:09 GMT
References: <12606@pt.cs.cmu.edu> <1991Apr12.015503.28001@dhw68k.cts.com>
Organization: Carnegie Mellon
Lines: 20

In article <1991Apr12.015503.28001@dhw68k.cts.com> stein@dhw68k.cts.com (Rick 'Transputer' Stein) writes:
>>Kung's "Law" says that if you scale node performance, without
>>increasing communication bandwidth, then nodes require more memory:
>>N, N^2 or even N^3 as much, depending on algorithm.
>Can you provide a literature reference on this "law?"

"Memory Requirements for Balanced Computer Architectures"
H.T. Kung
13th Annual International Symposium on Computer Architecture
1986, Tokyo

I think it's also a CMU tech report, and I believe he published
something similar in the Journal of Complexity.

Sorry to take so long to respond: deadlines.



-- 
Don		D.C.Lindsay 	Carnegie Mellon Robotics Institute