Search

Pre-execution is a promising latency tolerance technique that uses one or more helper threads running in spare hardware contexts ahead of the main computation to trigger long-latency memory operations early, hence absorbing their latency on behalf of the main computation. This article investigates several source-to-source C compilers for extracting pre-execution thread code automatically, thus relieving the programmer or hardware from this onerous task. We present an aggressive profile-driven compiler that employs three powerful algorithms for code extraction. First, program slicing removes non-critical code for computing cache-missing memory references. Second, prefetch conversion replaces blocking memory references with non-blocking prefetch instructions to minimize pre-execution thread stalls. Finally, speculative loop parallelization generates thread-level parallelism to tolerate the latency of blocking loads. In addition, we present four "reduced" compilers that employ less aggressive algorithms to simplify compiler implementation. Our reduced compilers rely on back-end code optimizations rather than program slicing to remove non-critical code, and use compile-time heuristics rather than profiling to approximate runtime information (e.g., cache-miss and loop-trip counts). We prototype our algorithms on the Stanford University Intermediate Format (SUIF) framework and a publicly available program slicer, called Unravel [Lyle and Wallace 1997]. Using our prototype, we undertake a performance evaluation of our compilers on a detailed architectural simulator of an 8-way out-of-order SMT processor with 4 hardware contexts, and 13 applications selected from the SPEC and Olden benchmark suites. Our most aggressive compiler improves the performance of 10 out of 13 applications, reducing execution time by 20.9%. Across all 13 applications, our aggressive compiler achieves a harmonic average speedup of 17.6%. For our reduced compilers, eliminating program slicing and relying on back-end optimizations degrades performance minimally, suggesting that effective pre-execution compilers can be built without program slicing. Furthermore, without cache-miss profiles, we still achieve good speedup, 15.5%, but without loop-trip count profiles, we achieve a speedup of only 7.7%. Finally, our results show compiler-based pre-execution can benefit multiprogrammed workloads. Simultaneously executing applications achieve higher throughput with pre-execution compared to no pre-execution. Due to contention for hardware contexts, however, time-slicing outperforms simultaneous execution in some cases where individual applications make heavy use of pre-execution threads. Categories and Subject Descriptors: B.8.2 [Performance and Reliability]: Performance Analysis and Design Aids; C.0 [General]: modeling of computer architecture; system architectures; C.4 [Performance of Systems]: design studies; D.3.4 [Programming Languages]: Processors-compilers General Terms: Algorithms, Design, Experimentation, Performance, Measurement Additional Key Words and Phrases: Data prefetching, multithreading, program slicing, speculative loop parallelization, prefetch conversion, memory-level parallelism, pre-execution

Pointer-chasing applications tend to traverse composite data structures consisting of multiple independent pointer chains. While the traversal of any single pointer chain leads to the serialization of memory operations, the traversal of independent pointer chains provides a source of memory parallelism. This article investigates exploiting such interchain memory parallelism for the purpose of memory latency tolerance, using a technique called multi-chain prefetching. Previous works [Roth et al. 1998; Roth and Sohi 1999] have proposed prefetching simple pointer-based structures in a multi-chain fashion. However, our work enables multi-chain prefetching for arbitrary data structures composed of lists, trees, and arrays. This article makes five contributions in the context of multi-chain prefetching. First, we introduce a framework for compactly describing linked data structure (LDS) traversals, providing the data layout and traversal code work information necessary for prefetching. Second, we present an off-line scheduling algorithm for computing a prefetch schedule from the LDS descriptors that overlaps serialized cache misses across separate pointer-chain traversals. Our analysis focuses on static traversals. We also propose using speculation to identify independent pointer chains in dynamic traversals. Third, we propose a hardware prefetch engine that traverses pointer-based data structures and overlaps multiple pointer chains according to the computed prefetch schedule. Fourth, we present a compiler that extracts LDS descriptors via static analysis of the application source code, thus automating multi-chain prefetching. Finally, we conduct an experimental evaluation of compiler-instrumented multi-chain prefetching and compare it against jump pointer prefetching [Luk and Mowry 1996], prefetch arrays [Karlsson et al. 2000], and predictor-directed stream buffers (FSB) [Sherwood et al. 2000]. Our results show compiler-instrumented multi-chain prefetching improves execution time by 40% across six pointer-chasing kernels from the Olden benchmark suite [Rogers et al. 1995], and by 3% across four SPECint2000 benchmarks. Compared to jump pointer prefetching and prefetch arrays, multi-chain prefetching achieves 34% and 11% higher performance for the selected Olden and SPECint2000 benchmarks, respectively. Compared to PSB, multi-chain prefetching achieves 27% higher performance for the selected Olden benchmarks, but PSB outperforms multi-chain prefetching by 0.2% for the selected SPECint2000 benchmarks. An ideal PSB with an infinite Markov predictor achieves comparable performance to multi-chain prefetching, coming within 6% across all benchmarks. Finally, speculation can enable multi-chain prefetching for some dynamic traversal codes, but our technique loses its effectiveness when the pointer-chain traversal order is highly dynamic. Categories and Subject Descriptors: B.8.2 [Performance and Reliability]: Performance Analysis and Design Aids; B.3.2 [Memory Structures]: Design Styles--Cache memories; C.0 [General]: Modeling of computer architecture; system architectures; C.4 [Performance of Systems]: Design studies; D.3.4 [Programming Languages]: Processors--Compilers General Terms: Design, Experimentation, Performance Additional Key Words and Phrases: Data prefetching, memory parallelism, pointer-chasing code

Objectives: This study aimed to reveal the epidemiologic characteristics of the outbreak of gastroenteritis caused by Salmonella enterica serovar Thompson in Busan Metropolitan City and to identify points for improvement to prevent of food-borne disease outbreak.Methods: This was a case-control study. The control group comprised asymptomatic students in the same classes of the cases. The presence or absence of symptoms, ingestion of each food provided by school meal service, and commonly ingested foods in addition to those foods in meal service were investigated. Moreover, specimens collected from rectal swab, preserved foods, and environmental surface were tested.Results: Of the 6,092 subjects, 1,111 (1,083 students, 22 school personnel, and 6 foodservice employees) were included in the case group; this corresponded to an 18.4% attack rate. Symptoms included diarrhea (n=1,051, 94.6%), abdominal pain (n=931, 83.8%), febrile sensation (n=502, 45.2%), and vomiting (n=275, 24.8%). The epidemic curves of each 10 schools were unimodal. Investigation of food intake showed a significantly high odds ratio for chocolate cake in 5 out of the 10 schools. Laboratory test detected Salmonella enterica serovar Thompson both in rectal swab specimens of 9 schools and in collected preserved chocolate cakes of 9 schools. Pulsed-field gel electrophoresis test result showed that Salmonella enterica seorvar Thompson isolated from human and foods were the same.Conclusions: The source of infection for the Salmonella enterica serovar Thompson outbreak in the 10 schools of Busan Metropolitan City is chocolate cake. Traceback investigation for origin of contaminated food in food-borne disease outbreak and safety control during food production should be more enhanced. [ABSTRACT FROM AUTHOR]