dhepner@hpisod2.HP.COM (Dan Hepner) (11/29/89)
From: brooks@maddog.llnl.gov (Eugene Brooks) >A real computer will have handful of Killer Micros hooked >up to a coherent cache system >A supercomputer will have a scalable >coherent cache system Is a coherent cache system essential or just nice? And why? Thanks, Dan Hepner
brooks@maddog.llnl.gov (Eugene Brooks) (12/01/89)
In article <13910002@hpisod2.HP.COM> dhepner@hpisod2.HP.COM (Dan Hepner) writes: >Is a coherent cache system essential or just nice? And why? It is essential if your cost of computing is dominated by software development costs. A system with large coherent caches allows you to exploit data locality by suitably mapping processors to the data set, but still allows the maintenance of a shared memory programming environment. At our laboratory, the cost of coding dominates the cost of computing by about a factor of 5. Coding cost is a very high priority issue because of this. The situtation may be different in other environments, ours may be unique with respect to the complexity of physical simulation codes and the daily modifications to them that occurs to support new physics as the designers who use the codes run their problems. brooks@maddog.llnl.gov, brooks@maddog.uucp
eugene@orville.nas.nasa.gov (Eugene Miya) (12/06/89)
>In article <13910002@hpisod2.HP.COM> dhepner@hpisod2.HP.COM (Dan Hepner) writes: >>Is a coherent cache system essential or just nice? And why? Depends if you want "consistent" results. If you can rely on heuristics like asynchronous chaotic relaxation (do you really want to call this an algorithm? [Baudet 1980] then NO. Otherwise, I think most people will answer YES (for consistent results). --eugene miya
afgg6490@uxa.cso.uiuc.edu (12/07/89)
>If you can rely on heuristics like asynchronous chaotic relaxation >(do you really want to call this an algorithm? [Baudet 1980] then NO. >Otherwise, I think most people will answer YES (for consistent results). > >--eugene miya Can you give a fuller reference for [Baudet 1980], and perhaps other asynchronous algorithms... (I suppose that I should check in your bibliography, Eugene, except I don't have it (some things had to give when I moved from the corporate womb). I would rather like to write a paper entitled "On the Potential Uses of Invalid Data"... Andy Glew aglew@uiuc.edu
dhepner@hpisod2.HP.COM (Dan Hepner) (12/09/89)
> >>Is a coherent cache system essential or just nice? And why? > > Depends if you want "consistent" results. >--eugene miya > I would rather like to write a paper entitled "On the Potential Uses > of Invalid Data"... > > Andy Glew aglew@uiuc.edu I doubt either one of you would be slowed down all that much in implementing a semaphore in an incoherent cache hardware environment. You'll have to have the ability to initiate local cache flush from software. Once you had the semaphore, you wouldn't have much trouble figuring out how to consistently get the right answer. This isn't an exotic type question, although like Andy, I thought the asynchronous reference sounded interesting. Eugene Brooks' extra software development answer sure makes sense, but once the semaphore is implemented, one might enquire as to just what the extra software development consists of. I.e. the programming paradigm wouldn't seem to be that different, and might be limited to combining a cache flush with the release of the lock protecting concurrent access to the shared resource. Since the acquisition of such a lock would seem likely even in a coherent design, why would software development be fundamentally more difficult? Dan Hepner
lkaplan@bbn.com (Larry Kaplan) (12/10/89)
In article <4095@amelia.nas.nasa.gov> eugene@orville.nas.nasa.gov (Eugene Miya) writes: >>In article <13910002@hpisod2.HP.COM> dhepner@hpisod2.HP.COM (Dan Hepner) writes: >>>Is a coherent cache system essential or just nice? And why? > >Depends if you want "consistent" results. > >If you can rely on heuristics like asynchronous chaotic relaxation >(do you really want to call this an algorithm? [Baudet 1980] then NO. >Otherwise, I think most people will answer YES (for consistent results). > >--eugene miya Let's take a little more serious attitude to this question. Coherent caches are certainly necessary if one wants correct results for the majority of parallel programs if cacheing of shared data is desired. The real question is whether the coherent cache support MUST be in hardware or whether a software solution is acceptable. In the context of KILLER MICROS, bus based systems, and therefore the related bus-based hardware consistency schemes, seem to run out of bandwidth after about 30 processors or so. Looking at a more scalable architecture, such as a shuffle-exchange network, broadcast invalidates tend to flood the interconnection network. Directory based schemes that try and keep track of who has what in their cache thereby allowing selective invalidates, are the best I've heard of so far but they are still very expensive to implemented. Lots of other research is going on to see how to do this job cheaply enough to make it commercially viable. I know of no currently released hardware cache consistent machines larger than 30+ processors. Software schemes can be constructed based on invalidating and locking and then unlocking and flushing shared data structures. These schemes are good because they cause no more memory traffic (or interconnection network traffic) than is necessary. Making the programmer use these schemes causes some extra coding effort though I could imagine adding compiler support for a new storage class that would automatically handle the protocol. No additional hardware is needed other than cheap synchronizing locks and the ability to explicitly invalidate and flush the cache. BBN is currently recommending a software based scheme for users that want to cache shared data on the TC2000. The kernel default caching policy is to not cache shared data, though the user may override this. _______________________________________________________________________________ ____ \ / ____ Laurence S. Kaplan | \ 0 / | BBN Advanced Computers lkaplan@bbn.com \____|||____/ 10 Fawcett St. (617) 873-2431 /__/ | \__\ Cambridge, MA 02238