Newsgroups: comp.parallel From: Charles Viles Subject: Scalability Summary (relatively long) Organization: University of Virginia Computer Science Department Date: Tue, 14 Sep 1993 22:48:00 GMT Folks, Here is the summary of replies I received concerning scalability and how to measure it. There are a number of good refs to papers in the literature and to papers that are in-press. Everyone seems to agree that its an over-loaded term to some extent. Systems people tend to assume the existence of a scalable problem and concentrate on how well a particular architecture does on the problem. Algorithms people look at things in the reverse manner. Also, *everyone* interpreted the question in the high-performance parallel machine domain as opposed to some other domain where the objective function is something other than some form of speedup metric. There are some concrete definitions and interpretations around. The March 1991 CACM article is a good one for an overview . I haven't had a chance to dig out any of the non-CACM ones yet. Here are the replies. Charlie ----------------------------------------------- From: kong@CS.UCLA.EDU (Kong Li) To: clv2m@uvacs.cs.virginia.edu Cc: Subject: Re: Scalability. What is it and how do we measure it? Date: Fri, 10 Sep 93 10:24:43 -0700 There is a "Scalability" column within the article "Ultra Computers" by Gordon Bell on pp.32-35 in CACM, Aug. 92, Vol. 35, No. 8. There are a few basic definitions for scalability. Kong Kong Li UCLA Computer Science Department kong@cs.ucla.edu ..!{uunet,ucbvax,rutgers,cepu}!cs.ucla.edu!kong ----------------------------------------------- From: fpst@hubcap.clemson.edu (Steve Stevenson) To: clv2m@uvacs.cs.virginia.edu Subject: Scalability. What is it and how do we measure it? Date: Fri, 10 Sep 93 10:21:56 -0400 I think you're barking up the wrong tree. It's the algorithm and architecture. A problem is scalable iff its solution (algorithm) can be put on and make use of varying numbers of processes. Architecture then comes into play when the question comes about: how fast does it run. steve ----------------------------------------------- Reply-to: clv2m@cs.virginia.edu Full-Name: Charles Viles To: fpst@hubcap.clemson.edu (Steve Stevenson) Subject: Re: Scalability. What is it and how do we measure it? > I think you're barking up the wrong tree. It's the algorithm and > architecture. A problem is scalable iff its solution (algorithm) can be > put on and make use of varying numbers of processes. Architecture then > comes into play when the question comes about: how fast does it run. But if you have a scalable problem you can still be hosed by an unscalable architecture (like a bunch of processors on a single bus ... eventually you can't add any more processors because the bus is swamped. The problem remains scalable.). So I think you *can* talk about scalable architectures and I don't think you can do so outside of the context of a particular application. Part of my point in the post was that no one agrees on what scalability and scalable mean. I took a straw poll on my department and came up with half a dozen related but different ideas. The algorithms folks interpreted things in terms of scalable problems. The systems people implicitly assumed you have a scalable problem and you want a architecture upon which to implement it. > steve Charlie ----------------------------------------------- From: fpst@hubcap.clemson.edu (Steve Stevenson) To: clv2m@uvacs.cs.virginia.edu Subject: Scalability. What is it and how do we measure it? Date: Fri, 10 Sep 93 16:17:31 -0400 I didn't say you couldn't get messed up by a bad architecture----I merely suggest that architecture is only one dimension. steve ----------------------------------------------- From: Mark Hahn To: clv2m@uvacs.cs.virginia.edu (Charles Viles) Subject: Re: Scalability. What is it and how do we measure it? Date: Fri, 10 Sep 93 12:24:44 -0400 in computer architecture, scalable means two things: in a parallel computer, that the interconnect (and thus number of processors) is expandable without hurting the performance characteristic. in a single processor, it means that the designers tried to avoid features that would bite them in future development. regards, mark hahn. ----------------------------------------------- From: Anshul Gupta To: clv2m@uvacs.cs.virginia.edu Cc: Subject: Re: Scalability. What is it and how do we measure it? Date: Sat, 11 Sep 93 00:24:34 CDT I can give you a few pointers in literature that would answer most of your questions. I am including only four references here, but the 2nd and the 3rd reference below contain very extensive bibliographies on the subject. Hope this helps. -Anshul Gupta Department of Computer Science University of Minnesota Minneapolis, MN 55455 @article{GUPTA93fft, AUTHOR = {Anshul Gupta and Vipin Kumar}, JOURNAL = {IEEE Transactions on Parallel and Distributed Systems}, NOTE = {A detailed version available as Technical Report TR 90-53, Department of Computer Science, University of Minnesota, Minneapolis, MN }, NUMBER = {7}, TITLE = {The scalability of {FFT} on Parallel Computers}, VOLUME = {4}, YEAR = {July 1993} } @techreport{KUMAR91scale, AUTHOR = {Vipin Kumar and Anshul Gupta}, INSTITUTION = {Department of Computer Science Department, University of Minnesota, Minneapolis, MN}, NOTE = {To appear in {\em Journal of Parallel and Distributed Computing}, 1994. A shorter version appears in {\em Proceedings of the 1991 International Conference on Supercomputing}}, NUMBER = {TR 91-18}, TITLE = {Analyzing Scalability of Parallel Algorithms and Architectures}, YEAR = {1991} } @book{KUMAR93book, ADDRESS = {Redwood City, CA}, AUTHOR = {Vipin Kumar and Ananth Grama and Anshul Gupta and George Karypis}, PUBLISHER = {Benjamin/Cummings}, TITLE = {Introduction to Parallel Computing: Design and Analysis of Algorithms}, YEAR = {1993} } @article{ANANTH93iso, AUTHOR = {Ananth Grama and Anshul Gupta and Vipin Kumar}, JOURNAL = {IEEE Parallel and Distributed Technology, Special Issue on Parallel and Distributed Systems: From Theory to Practice}, NOTE = {Also available as Technical Report TR 93-24, Department of Computer Science, University of Minnesota, Minneapolis, MN}, TITLE = {Isoefficiency Function: A Scalability Metric for Parallel Algor ithms and Architectures}, YEAR = {1993 (To Appear)} } ----------------------------------------------- From: jones@hermes.chpc.utexas.edu (William L. Jones) To: clv2m@uvacs.cs.virginia.edu Cc: Subject: Re: Scalability. What is it and how do we measure it? Date: Sat, 11 Sep 93 15:22:35 -0500 You should read the paper by Patrick H. Worley paper of January 1989 "THE EFFECT OF TIME CONSTRAINTS ON SCALED SPEED-UP" - ORNL/TM-11031 It is a Oak Ridget Naitnal Laboratory document. You should be able to right to: Oak Ridget National Laboratory Mathematical Sciences Section P.O. Box 2009, Bldg. 9207-A Oak Ridget, TN 37831-8083 to get a copy. It makes some very important points. Best is not all problems scale the same. I also points out that even though a problem might be scalable this fact may not be usable. He has a very nice example of a problem thatis scalable but who run time increase by 12*N where N is the number of process. If the problem time took 1 hr for one processes you would be waiting 512 day for the answer for the scalled up problem on 1024 node system. The biggest problem that I see right now with people in copmutingh parallel is their lack are of understanding how various problems scale. If you have Jack. J. Dongarra "Perormance of Various Computers Using Standard Linear Equations Software" look at table 3 and ask yourself why all the very large MPP can only get about half their peek performance on a unconstrained problem. I suppect its an inherent property of the problem. Unless you do the same sort of analysis of the problem as Patrick H. Worley did you won't know and you may be doomed for every tring to squeeze more speed out of problem that is rock dry. I do believe MPP system can be cost effective. I don't believe that they will be until we get a better understanding of how problems scale to MPP systems. Bill Jones ----------------------------------------------- From: A.D.Ben-Dyke@computer-science.birmingham.ac.uk To: Charles Viles Subject: Re: Scalability. What is it and how do we measure it? Date: Mon, 13 Sep 93 13:02:56 BST Charles, Two articles that may interest you are: @Article{Mach:Scalability, author = {Daniel Nussbaum and Anant Agarwal}, title = {Scalability of Parallel Machines}, journal = {communications of the ACM}, year = {1991}, month = {March}, volume = {34}, number = {3}, pages = {56-62}, annote = {Details the shortcomings of the existing definitions of scalability before setting out the criteria for a useful definition: 1. express the effects of the interconnection network and the comms pattern of the algorithm; 2. scalability of a machine with respect to a particular algorithm; 3. Distinguish between algorithmic scalability (based on CREW PRAM) and the machines scalability wrt the algorithm; 4. Comms speed is taken into account; 5. measure the best achievable performance without regard to cost or efficiency 6. Yield several levels of info: how it failed, where it succeeded etc}, got = {yes}, } @Article{Define:Scalability, author = {Mark D. Hill}, title = {What is Scalability?}, institution = {University of Wisconsin}, journal = {Computer Architecture News}, year = {1990}, volume = {18}, pages = {18--21}, email = {markhill@cs.wisc.edu}, annote = {Poses many questions as to what scaslability actually measures, including: is an arch scalable, can some archs be more scalable than others, does workload affect scaling, cost?, who must consider scalability etc.? Then an attempt is made to define scalability, firstly in terms of efficiency and speedup, based on theoretical models, but then using more realistics measurements. However, no satisfactory result is arrived at and there is a call for further work or for dropping the catch all label from the literature.}, got = {yes}, } I'd be very interested in any other replies you get. Cheers, Andy. ----------------------------------------------- From: lindsay+@cs.cmu.edu (Donald Lindsay) Subject: Re: Scalability. What is it and how do we measure it? Message-ID: <1993Sep13.152612.13345@hubcap.clemson.edu> Sender: fpst@hubcap.clemson.edu (Steve Stevenson) Organization: School of Computer Science, Carnegie Mellon Follow-Up: comp.parallel Date: Mon, 13 Sep 93 11:26:12 EDT Approved: parallel@hubcap.clemson.edu In article <1993Sep10.142930.15704@hubcap.clemson.edu> Charles Viles writes: >What *is* scalability? > How about: > The ability of an architecture to continue to meet application > requirements under increasing load. The word means several different things, in different contexts. A vendor of multiprocessors will use it to mean that you can buy a small system, and later tack on more processors. In a similar sense, a machine with high IO capacity can usefully be scaled by buying more IO devices. I've heard the success of Tandem ascribed to the fact that their products are "plastic", by which the gentleman meant, malleable. A configuration could be edited quite freely - add to a cluster, add clusters, make a disk be mirrored. So, this is scalability on quite different axes - compute, storage, reliability, physical distribution - and at an application level. From this, we see that "scalable" has wandered off from the "system" or "machine" architecture, and we have new realms with which to cause verbal confusion. The S in SPARC stands for yet another meaning. The idea here was that the architects of the instruction set had carefully considered what future implementations might be like. By designing out all impediments, they had (they said) allowed these future implementations to be designed more rapidly. Since chip technology is moving rapidly, this would allow SPARC-based products to "track" rather than lag. Hence, SPARC was "scalable". I don't see any way to bring the word back to a single meaning. At best, you can get agreement within some specific context. -- Don D.C.Lindsay Carnegie Mellon Computer Science -- Charles Viles (clv2m@virginia.edu) Department of Computer Science University of Virginia Charlottesville, VA 22902 ----------------------------------------------- Newsgroups: comp.parallel,comp.arch From: lamaster@pioneer.arc.nasa.gov (Hugh LaMaster) Subject: Re: Scalability. What is it and how do we measure it? Organization: NASA Ames Research Center, Moffett Field, CA Date: Thu, 16 Sep 1993 13:28:48 GMT In article <1993Sep10.142930.15704@hubcap.clemson.edu>, Charles Viles writes: |> What *is* scalability? |> How about: |> The ability of an architecture to continue to meet application |> requirements under increasing load. You will enjoy reading the article by Mark D. Hill, of U. of Wisc., "What is Scalability?", in "Scalable Shared-Memory Multiprocessors" - a book based on some workshop proceedings. This may also have appeared in SIGARCH, Dec. 1990. The book is edited by Michel Dubois and Shreekant Thakker. Lib. of Congr. # QA76.5.S244 1991) -- Hugh LaMaster, M/S 233-9, UUCP: ames!lamaster NASA Ames Research Center Internet: lamaster@ames.arc.nasa.gov Moffett Field, CA 94035-1000 Or: lamaster@george.arc.nasa.gov Phone: 415/604-1056 #include ----------------------------------------------- Newsgroups: comp.parallel From: stiles@stiles.ee.usu.edu (Dyke Stiles) Subject: Scalability summary..... Date: Thu, 16 Sep 1993 13:27:36 GMT There is a very good article on the problems of scaling algorithms by Singh, Hennessy, and Gupta in the July 93 issue of IEEE Computer - pp. 42-50. It emphasizes that there are MANY factors that need to be considered... Dyke Stiles stiles@cc.usu.edu