2/458: Parallel and Distributed Systems Jan. 29 - Feb. 10, 2003 Parallelization reading assignments for Mon. 3 Feb: Lauer & Needham Welsh et. al from SOSP 2001 for Mon. 10 Feb: Crowl et al. student projects, presentations need to choose class topic (and date) by Mon. 10 Feb project proposal by Wed. 26 Feb. guest class leaders Feb. 17 and 19: Amy Murphy -- mobile computing Kai Shen -- clustered servers --------------------------- ticket locks proportional backoff fairness for locks: advantages and disadvantages preemption in line counter results how common are races? how expensive are pthread locks? how do the others compare? is FAI a clear win? what happens with # of threads just above or below the # of processors? ========================================================== Describing parallel performance How do we know if something is parallelizing well? Should we expect things to run twice as fast on twice as many processors? Measures: let T(1) be the time to solve our favorite problem on 1 processor, using the best available single-processor algorithm let T(p) be the time to solve it on our p-processor machine with a parallel algorithm speedup S = T(1)/T(p) (effective processors) efficiency E = S/p How to lie with statistics: cripple the sequential program. This is a *very* common practice: people compare the performance of their parallel program on p processors to its performance on 1 processor, as if this told you something you care about, when in reality their parallel program on one processor runs *much* slower than the best known sequential program does. Moral: anytime anybody shows you a speedup curve, demand to know what algorithm they're using in the numerator. Amdahl's law: model performance as serial portion T_s + parallel(izable) portion T_p total work c = T_s + T_p = T(1) T(p) = T_s + T_p/p S = (T_s + T_p) / (T_s + T_p/p) = c / (T_s + T_p/p) --> c / T_s as p --> oo --------------------- This looks like terrible news! But: do we want a given problem to run faster, or do we want to solve bigger problems? Folks at Sandia national labs have argued [CACM May 1988] that bigger machines are used for bigger problems [Often true, though not always; consider weather prediction: Existing mathematical models can provide an "acceptably good" prediction of tomorrow's weather based on today's measurements, but require many days of computing (I'm not sure exactly how many). With a bigger machine, we want to solve a given problem faster. Suppose we cross the threshold, however, and can get our acceptably good prediction in a couple hours. Then things will change qualitatively: we'll want to reduce the grid size of the fluid dynamics code to get a better quality prediction.] Note that the problem size is often under direct programmer control in scientific applications -- it may mean larger experiments (e.g. bigger galaxies) or greater accuracy (e.g. finer grids). propose concept of "scaled speedup": constant total time T_s + T_p [ note new meaning for T_p ] total work = T_s + pT_p [ assuming we scale prob. size lin. with p ] total work (T_s + pT_p) scaled speedup = ---------- = ------------ total time (T_s + T_p) (T_s + pT_p) (T_s + (c-T_s)p) = ------------ = ---------------- = p (1 - T_s/c) + T_s/c c c which rises linearly with p, which is nice [NB: "linear speedup" is generally taken to mean speedup that is not only linear, but that has a constant very close to 1. This is an abuse of terminology, but probably too pervasive to reverse.] ------------------ There has been quite a lot of discussion over the years of speedup "anomalies", particularly reports of the occurrence of (or impossibility of!) "superlinear" speedup. Helmbold and McDowell [TPDS Apr. 1990] provide a formal model of speedup that captures these seemingly contradictory results. They note that "linear subunitary scaled speedup is possible even in the presence of sequential work... [whereas in the] nonscaled case... [speedup] is always bounded by a constant in the presence of sequential work." They also categorize sources of speedup anomalies: 1 reduced overhead -- some operations get cheaper because you've got fewer processes per processor 2 increasing cache size -- similar to the above: memory latency appears to go down because the total aggregate cache size went up 3 latency hiding -- if you have multiple processes per processor, you can do something else while waiting for a slow remote op to complete 4 randomization -- simultaneous speculative pursuit of several possible paths to a solution It should be noted that anytime "superlinear" speedup occurs for reasons 3 or 4, the sequential algorithm could (given free context switches) be made to run faster by mimicing the parallel algorithm. This is sometimes practical, e.g. wrt speculative computation in combinatorial search (see Tom's lecture next week). ========================================================== Lauer and Needham Observations about address spaces (one per process in message-oriented system) should usually be thought of in terms of language referencing environment, rather than HW protection domain -- we don't necessarily change page tables when changing processes. Note at top of p. 6 is key: "...processes [in a message-oriented system] tend to be associated with system resources, and the needs of applications which the system exists to serve are encoded into data to be passed around in messages." Other examples of a message-oriented systems: Minix and Amoeba. In those systems one of the heavyweight processes represents *all* user-level processes. Likewise note in the middle of p. 8: "...system resources [in a procedure-oriended system] tend to be encoded in common or global data structures and the applications are associated with processes whose needs are encoded in calls to system-provided procedures which access this data." Most modern OSes are procedure-oriented, including Linux, every commercial Unix I know of (including MacOS X), and Windows NT/2000/XP. Note that shared memory is still very useful in a message-oriented system: it makes message-passing fast (messages are little header blocks containing pointers to big data structures in shared memory). What L&N call "message channels" are sometimes called "output ports". What they call "message ports" are sometimes called "input ports". It is common, though not universal, for the connections among output ports and input ports to be many-one. L&N's performance arguments (p. 14) are "hand-wavy". In practice, people tend to build procedure-oriented kernels and message-oriented servers. Conventional wisdom holds that the alternatives are not as efficient. Why is this? Part of the answer, perhaps, is that event-driven servers don't really follow the L&N message-passing model. Rather than one process per logical resource or system component, they typically have one process per processor, which multiplexes management of multiple resources/components. In effect, the processes of the message-passing model are laid on top of each other, leading to one big process with a very large (heterogeneous, often hard to understand) switch statement. As a result, the event-driven model avoids most of the context switches of the message-passing model, for much improved performance. Q: could we build an event-driven kernel? Probably too complex; servers are hairy enough. Welsh et al. Message-based model as a compromise between the shared-memory model and the event-driven model. Draw picture. As the authors note, the event-driven model (and indeed the message-passing model as well) depends critically on not blocking during sub-tasks. It's not very tolerant of page faults, for example. Welsh et al. cite L&N at the top of p. 4. ========================================================== Crowl et al. combinatorial search paper the 7 machines the basic algorithm node (i, j) in the tree postulates that i maps to j; all nodes numbered smaller than i in S have had mappings postulated in ancestor nodes of the tree distance filter deals with *paths* if we guess that i maps to j we conclude that k does NOT map to l if the distance from i to k is less than the distance from j to l connectivity filter deals with *edges* if we guess that i maps to j we conclude that k does NOT map to l if there is an edge from i to k but not from j to l the argument: the "right" parallelization depends on the machine granularity of parallelism, communication overhead the problem whether you want one solution or all solutions the input data in this problem: whether the search space is so dense enough to justify focusing search, or whether speculation is better