{"content":[{"text":"lows application development on commodity hardware that \n can exploit the resources available on large-scale systems. \n Lightweight threading requires a lightweight synchro- \n nization model [9]. The model used by the Cray XMT and \n PIM designs, pioneered by the Denelcor HEP [15], uses ful- \n l/empty bits (FEBs). This technique marks each word in \n memory with a “full” or “empty” state, allows programs \n to wait for either state, and makes the state change atomi- \n cally with the word’s contents. This technique can be imple- \n mented directly in hardware, as it is in the XMT. Alterna- \n tives include ADA-like protected records [24] and fork-sync \n [4], which lack a clear hardware analog. \n This paper discusses programming models’ impact \n on efﬁcient multithreading and the resource management \n necessary for those models. It introduces the qthread \n lightweight threading API and its Unix implementation. \n The API is designed to be a lightweight threading standard \n for current and future architectures. The Unix implementa- \n tion is a proof of concept that provides a basis for develop- \n ing applications for large scale multithreaded architectures.","bbox":{"left":0.081882,"top":0.091865,"width":0.386035,"height":0.30196100000000003}},{"text":"The equal distribution solution is also simple: divide \n the array equally among all of the available processors and \n spawn a thread for each. Each thread must sum its segment \n serially and return the result. The parent thread sums the \n return values. This technique is efﬁcient because it matches \n the needed parallelism to the available parallelism, and the \n processors do minimal communication. However, equal \n distribution is not particularly tolerant of other load imbal- \n ances: execution is as slow as the slowest thread. \n The lagging-loop model relies upon arbitrary workload \n divisions. It breaks the array into small chunks and spawns \n a thread for each chunk. Each thread sums its chunk and \n then waits for the preceding thread (if any) to return an an- \n swer before combining the sum and returning its own total. \n Eventually the parent thread will do the same with the last \n chunk. This model is more efﬁcient than the tree model, \n and the number of threads depends on the chunk size. The \n increased number of threads makes it more tolerant of load \n imbalances, but has more overhead.","bbox":{"left":0.504676,"top":0.091865,"width":0.386035,"height":0.286983}},{"text":"2.2. Handling resource exhaustion","bbox":{"left":0.504676,"top":0.393829,"width":0.25952200000000003,"height":0.018002000000000018}},{"text":"2.","bbox":{"left":0.081882,"top":0.410203,"width":0.014650999999999997,"height":0.019639000000000018}},{"text":"Recursive threaded programming \n and resource management","bbox":{"left":0.106633,"top":0.410203,"width":0.29257,"height":0.03724900000000003}},{"text":"models","bbox":{"left":0.409302,"top":0.410203,"width":0.05860399999999999,"height":0.019639000000000018}},{"text":"These methods differ in the way resources must be man- \n aged to guarantee forward progress. Whenever new thread \n is requested, one of four things can be done:","bbox":{"left":0.504676,"top":0.427288,"width":0.3860349999999999,"height":0.045348}},{"text":"Managing large numbers of threads requires managing \n per-thread resources, even if those requirements are low. \n This management can affect whether multithreaded appli- \n cations run to completion and whether they execute faster \n than an equivalent serial implementation. The worst conse- \n quence of poor management is deadlock: if more threads \n are needed than resources are available, and reclaiming \n thread resources depends on spawning more threads, the \n system cannot make forward progress.","bbox":{"left":0.081882,"top":0.462568,"width":0.386035,"height":0.13591799999999998}},{"text":"1. \n 2. \n 3. \n 4.","bbox":{"left":0.516885,"top":0.482987,"width":0.012209000000000025,"height":0.06044299999999997}},{"text":"Execute the function inline. \n Create a new thread. \n Create an record that will become a thread later. \n Block until sufﬁcient resources are available.","bbox":{"left":0.537234,"top":0.482987,"width":0.312373,"height":0.06044299999999997}},{"text":"In a large enough parallel program, eventually the resources \n will run out. Requests for new threads must either block un- \n til resources become available or must fail and let the pro- \n gram handle the problem. \n Blocking to wait for resources to become available af- \n fects each parallel model differently. The lagging loop \n method works well with blocking requests, because the \n spawned threads don’t rely on spawning more threads. \n When these threads complete, their resources may be \n reused, and deadlock is easily avoided. The equal distri- \n bution method has a similar advantage. However, because \n it avoids using more than the minimum number of threads, \n it does not cope as well with load imbalances. \n The recursive tree method gathers a lot of state quickly \n and slowly releases it, making the method particularly sus- \n ceptible to resource exhaustion deadlock, where all run- \n ning threads are blocked spawning more threads. In order \n to guarantee forward progress, resources must be reserved \n when threads spawn and threads must execute serially when \n reservation fails. The minimum state that must be reserved \n is the amount necessary get to the bottom of the recursive \n tree serially. Thus, if there are only enough resources for a \n single depth-ﬁrst exploration of the tree, recursion may only","bbox":{"left":0.504676,"top":0.553782,"width":0.386035,"height":0.34748}},{"text":"2.1. Parallel programming models","bbox":{"left":0.081882,"top":0.612296,"width":0.259629,"height":0.018001999999999962}},{"text":"An illustrative example of the effect the programming \n model on resource management is the trivial problem of \n summing integers in an array. A serial solution is trivial: \n start at the beginning, and tally each sequential number un- \n til the end of the array. There are at least three parallel ex- \n ecution models that could compute the sum. They can be \n referred to as the recursive tree model, the equal distribu- \n tion model, and the lagging-loop model. \n A recursive tree solution to summing the numbers in an \n array is simple to program: divide the array in half, and \n spawn two threads to sum up both halves. Each thread does \n the same until its array has only one value, whereupon the \n thread returns that value. Thread that spawned threads wait \n for their children to return and return the sum of their values. \n This technique is parallel, but uses a large amount of state. \n At any point, most of the threads are not doing useful work. \n While convenient, this is a wasteful technique.","bbox":{"left":0.081882,"top":0.644586,"width":0.386035,"height":0.256676}}],"images_bbox":[],"images_bbox_not_text_overlap":[]}