Show simple item record

Efficient Multiprogramming for Multicores with SCAF

dc.contributor.advisorBarua, Rajeev Ken_US
dc.contributor.authorCreech, Timothy Mattauschen_US
dc.date.accessioned2016-02-09T06:32:21Z
dc.date.available2016-02-09T06:32:21Z
dc.date.issued2015en_US
dc.identifierhttps://doi.org/10.13016/M2RB19
dc.identifier.urihttp://hdl.handle.net/1903/17348
dc.description.abstractAs hardware becomes increasingly parallel and the availability of scalable parallel software improves, the problem of managing multiple multithreaded applications (processes) becomes important. Malleable processes, which can vary the number of threads used as they run, enable sophisticated and flexible resource management. Although many existing applications parallelized for SMPs with parallel runtimes are in fact already malleable, deployed run-time environments provide no interface nor any strategy for intelligently allocating hardware threads or even preventing oversubscription. Prior research methods either depend upon profiling applications ahead of time in order to make good decisions about allocations, or do not account for process efficiency at all, leading to poor performance. None of these prior methods have been adapted widely in practice. This paper presents the Scheduling and Allocation with Feedback (SCAF) system: a drop-in runtime solution which supports existing malleable applications in making intelligent allocation decisions based on observed efficiency without any changes to semantics, program modification, offline profiling, or even recompilation. Our existing implementation can control most unmodified OpenMP applications. Other malleable threading libraries can also easily be supported with small modifications, without requiring application modification or recompilation. In this work, we present the SCAF daemon and a SCAF-aware port of the GNU OpenMP runtime. We present a new technique for estimating process efficiency purely at runtime using available hardware counters, and demonstrate its effectiveness in aiding allocation decisions. We evaluated SCAF using NAS NPB parallel benchmarks on five commodity parallel platforms, enumerating architectural features and their effects on our scheme. We measured the benefit of SCAF in terms of sum of speedups improvement (a common metric for multiprogrammed environments) when running all benchmark pairs concurrently compared to equipartitioning --- the best existing competing scheme in the literature. If the sum of speedups with SCAF is within 5% of equipartitioning (i.e., improvement factor is 0.95X < improvement factor in sum of speedups < 1.05X), then we deem SCAF to break even. Less than 0.95X is considered a slowdown; greater than 1.05X is an improvement. We found that SCAF improves on equipartitioning on 4 out of 5 machines, breaking even or improving in 80-89% of pairs and showing a mean improvement of 1.11-1.22X for benchmark pairs for which it shows an improvement, depending on the machine. Since we are not aware of any widely available tool for equipartitioning, we also compare SCAF against multiprogramming using unmodified OpenMP, which is the only environment available to end-users today. SCAF improves or breaks even on the unmodified OpenMP runtimes for all 5 machines in 72-100% of pairs, with a mean improvement of 1.27-1.7X, depending on the machine.en_US
dc.language.isoenen_US
dc.titleEfficient Multiprogramming for Multicores with SCAFen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentElectrical Engineeringen_US
dc.subject.pqcontrolledComputer engineeringen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pqcontrolledElectrical engineeringen_US
dc.subject.pquncontrolledcompilersen_US
dc.subject.pquncontrolledmultiprogrammingen_US
dc.subject.pquncontrolledmultithreadingen_US
dc.subject.pquncontrolledoperating systemsen_US
dc.subject.pquncontrolledparallelen_US
dc.subject.pquncontrolledruntime environmentsen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record