Notes for CSC 2/456 (Computer Systems), Wednesday 4-19-2000ff ========================================================== Parallel machines/architectures Granularity of parallelism instruction level parallelism (ILP) -- overlap instructions transparent pipelining superscalar out-of-order execution esplicit vectors VLIW/EPIC SIMD Connection machine, MASPAR, DataCube, etc. multi-threaded -- overlap computation with memory access HEP/Tera Alewife several other research designs MIMD multicomputers (message-based) and multiprocessors (shared memory) multicomputers and multiprocessors motivation price-performance scalability upgradability tradeoffs multicomputers generally have lower unit cost and better scalability multiprocessors support more fine-grain operations and a more familiar programming model interconnection networks issues direct versus indirect multicomputer (big messages) versus multiprocessor (little messages) degree diameter packaging considerations mapping into two or three-dimensional space minimizing maximum wire length wormhole routing and virtual cut-through in direct networks hot spots in log-depth indirect networks bus ring star tree log-depth indirect butterfly (FFT): RP3, BBN, Cedar, Monarch FAT tree: CM5, SP2, Mercury many others (banyan, shuffle-exchange, ADM, omega) deBruijn 2^k nodes, degree = 4, diameter = k nodes connected to i are those whose numbers are i shifted one bit left or right, with a one or a zero shifted in 8-node example: 001 ------------- 011 / | \ / | \ 000 | 010 === 101 | 111 \ | / \ | / 100 ------------- 110 mesh ("NEWS" in 2 dimensions) torus hypercube cube-connected cycles where is the memory? local only (multicomputer) SP2, Beowulf global only ("dance hall") bus-based: Sun; small SGI, Sequent, Intel, ... larger (discredited): Monarch, Cedar, Ultracomputer NUMA coherent: SGI Origin, SCI (Sequent, Convex, ...), various research projects non-coherent: Cray, Mercury Cache coherence broadcast-based recall MESI protocol described earlier _ / \ read hit v | invalid <--bus write-once-- valid <--read miss-- ^ < > ^ | | \ / | | | bus \ / bus | | | write \ / read | | | miss \ / miss | | | / \ | | | / \ | | write | / \ | | hit | / \ | v write miss--> dirty <---write hit--- reserved | ^ \_/ write hit directory-based bitmap (DASH) fixed-size word list with software overflow (Alewife) linear chain (SCI) tree (proposed SCI extension) approximate bitmap (Origin) ================================ multiprocessor OSes master + slaves simplest approach doesn't scale past 2-3 processors (typical job mixes spend 30-40% of time in kernel) symmetric shared memory issues: granularity of locking (scalability) fault tolerance important early work done at Encore Irix the most scalable at present: up to 128 processors message-based varying levels of integration, from Solaris on network of Suns to AIX on SP-2 to V, Locus, Amoeba, etc. cellular (hybrid) Unicos-MP, Cellular Irix (SGI/Cray) Hive (research, Stanford) general issue of function shipping v. data shipping: which one wins depends on costs of communication and amount of info to ship. Example: make a process runnable on another node. modify ready list directly (requires MP-capable locks) send request, field in interrupt handler (requires IH-capable locks) send request, handle in top half (significant overhead) ================================ coherence and consistency coherence pertains to an individual location, possibly written by multiple processors consistency pertains to multiple locations, read and/or written by multiple processors sequential consistency essentially behaves as if there was a single serialized global memory and no caches processor consistency operations of a given processor are seen in order by everybody else; no other guarantees *fence* instructions to ensure that various things are globally visible release consistency notion of acquire and release operations all previous writes by local processor are globally visible before a release completes all previous writes by other processors are locally visible before an acquire completes lots of other variants ---------------- S-DSM first cut: do basically what hardware coherence does but: don't have access to cache state three main approaches: special API for shared memory software instrumentation VM false sharing VM-based systems with relaxed consistency benefit from multi-writer protocols require data-race-free programming model diffs