TY - RPRT TI - Speculation with Little Wasting: Saving Cost in Software Speculation Through Transparent Learning AU - Jiang, Yunlian AU - Shen, Xipeng A3 - Computer Science Department, The College of William and Mary DA - 2009/// PY - 2009/// M1 - WM-CS-2009-08 PB - Computer Science Department, The College of William and Mary SN - WM-CS-2009-08 ER - TY - RPRT TI - Streamlining GPU Applications On the Fly – Thread Divergence Elimination through Runtime Thread-Data Remapping AU - Zhang, Eddy Z. AU - Jiang, Yunlian AU - Guo, Ziyu AU - Shen, Xipeng A3 - Computer Science Department, The College of William and Mary DA - 2009/// PY - 2009/// M1 - WM-CS-2009-08 PB - Computer Science Department, The College of William and Mary SN - WM-CS-2009-08 ER - TY - RPRT TI - Co-Run Locality Prediction for Proactive Shared-Cache Management AU - Shen, Xipeng AU - Jiang, Yunlian A3 - Computer Science Department, The College of William and Mary DA - 2009/// PY - 2009/// M1 - WM-CS-2009-03 M3 - Technical Report PB - Computer Science Department, The College of William and Mary SN - WM-CS-2009-03 ER - TY - RPRT TI - A Systematic Measurement of the Influence of Non-Uniform Cache Sharing on the Performance of Modern Multithreaded Programs AU - Zhang, Eddy Z. AU - Jiang, Yunlian AU - Shen, Xipeng A3 - Computer Science Department, The College of William and Mary DA - 2009/// PY - 2009/// M1 - WM-CS-2009-04 M3 - Technical Report PB - Computer Science Department, The College of William and Mary SN - WM-CS-2009-04 ER - TY - RPRT TI - Program Seminal Behaviors: Automating Input Characterization for Large-Scope Proactive Behavior Prediction AU - Shen, Xipeng AU - Jiang, Yunlian AU - Zhang, Eddy Z. AU - Tan, Kai AU - Mao, Feng AU - Gethers, Malcom A3 - Computer Science Department, The College of William and Mary DA - 2009/// PY - 2009/// M1 - WM-CS-2009-07 M3 - Technical Report PB - Computer Science Department, The College of William and Mary SN - WM-CS-2009-07 ER - TY - CONF TI - Influence of program inputs on the selection of garbage collectors AU - Mao, Feng AU - Zhang, Eddy Z. AU - Shen, Xipeng T2 - the 2009 ACM SIGPLAN/SIGOPS international conference AB - Many studies have shown that the best performer among a set of garbage collectors tends to be different for different applications. Researchers have proposed application-specific selection of garbage collectors. In this work, we concentrate on a second dimension of the problem: the influence of program inputs on the selection of garbage collectors. C2 - 2009/// C3 - Proceedings of the 2009 ACM SIGPLAN/SIGOPS international conference on Virtual execution environments - VEE '09 DA - 2009/// DO - 10.1145/1508293.1508307 PB - ACM Press SN - 9781605583754 UR - http://dx.doi.org/10.1145/1508293.1508307 DB - Crossref ER - TY - CONF TI - A cross-input adaptive framework for GPU program optimizations AU - Liu, Yixun AU - Zhang, Eddy Z. AU - Shen, Xipeng T2 - Distributed Processing (IPDPS) AB - Recent years have seen a trend in using graphic processing units (GPU) as accelerators for general-purpose computing. The inexpensive, single-chip, massively parallel architecture of GPU has evidentially brought factors of speedup to many numerical applications. However, the development of a high-quality GPU application is challenging, due to the large optimization space and complex unpredictable effects of optimizations on GPU program performance. Recently, several studies have attempted to use empirical search to help the optimization. Although those studies have shown promising results, one important factor—program inputs—in the optimization has remained unexplored. In this work, we initiate the exploration in this new dimension. By conducting a series of measurement, we find that the ability to adapt to program inputs is important for some applications to achieve their best performance on GPU. In light of the findings, we develop an input-adaptive optimization framework, namely G-ADAPT, to address the influence by constructing cross-input predictive models for automatically predicting the (near-)optimal configurations for an arbitrary input to a GPU program. The results demonstrate the promise of the framework in serving as a tool to alleviate the productivity bottleneck in GPU programming. C2 - 2009/5// C3 - 2009 IEEE International Symposium on Parallel & Distributed Processing DA - 2009/5// DO - 10.1109/ipdps.2009.5160988 PB - IEEE SN - 9781424437511 UR - http://dx.doi.org/10.1109/ipdps.2009.5160988 DB - Crossref ER - TY - CONF TI - A study on optimally co-scheduling jobs of different lengths on chip multiprocessors AU - Tian, Kai AU - Jiang, Yunlian AU - Shen, Xipeng T2 - the 6th ACM conference AB - Cache sharing in Chip Multiprocessors brings cache contention among corunning processes, which often causes considerable degradation of program performance and system fairness. Recent studies have seen the effectiveness of job co-scheduling in alleviating the contention. But finding optimal schedules is challenging. Previous explorations tackle the problem under highly constrained settings. In this work, we show that relaxing those constraints, particularly the assumptions on job lengths and reschedulings, increases the complexity of the problem significantly. Subsequently, we propose a series of algorithms to compute or approximate the optimal schedules in the more general setting. C2 - 2009/// C3 - Proceedings of the 6th ACM conference on Computing frontiers - CF '09 DA - 2009/// DO - 10.1145/1531743.1531752 PB - ACM Press SN - 9781605584133 UR - http://dx.doi.org/10.1145/1531743.1531752 DB - Crossref ER - TY - JOUR TI - The Imprecise Dirichlet Model for Multilevel System Reliability AU - Wilson, Alyson G. AU - Huzurbazar, Aparna V. AU - Sentz, Kari T2 - Journal of Statistical Theory and Practice DA - 2009/3// PY - 2009/3// DO - 10.1080/15598608.2009.10411921 VL - 3 IS - 1 SP - 211-223 J2 - Journal of Statistical Theory and Practice LA - en OP - SN - 1559-8608 1559-8616 UR - http://dx.doi.org/10.1080/15598608.2009.10411921 DB - Crossref KW - Fault tree KW - Bayesian network KW - Multilevel data KW - Reliability KW - Multinomial-Dirichlet model KW - Imprecise Dirichlet model ER - TY - JOUR TI - The study and handling of program inputs in the selection of garbage collectors AU - Shen, Xipeng AU - Mao, Feng AU - Tian, Kai AU - Zhang, Eddy Zheng T2 - ACM SIGOPS Operating Systems Review AB - Many studies have shown that the best performer among a set of garbage collectors tends to be different for different applications. Researchers have proposed applicationspecific selection of garbage collectors. In this work, we concentrate on a second dimension of the problem: the influence of program inputs on the selection of garbage collectors. We collect tens to hundreds of inputs for a set of Java benchmarks, and measure their performance on Jikes RVM with different heap sizes and garbage collectors. A rigorous statistical analysis produces four-fold insights. First, inputs influence the relative performance of garbage collectors significantly, causing large variations to the top set of garbage collectors across inputs. Profiling one or few runs is thus inadequate for selecting the garbage collector that works well for most inputs. Second, when the heap size ratio is fixed, one or two types of garbage collectors are enough to stimulate the top performance of the program on all inputs. Third, for some programs, the heap size ratio significantly affects the relative performance of different types of garbage collectors. For the selection of garbage collectors on those programs, it is necessary to have a cross-input predictive model that predicts the minimum possible heap size of the execution on an arbitrary input. Finally, by adoptingstatistical learning techniques, we investigate the cross-input predictability of the influence. Experimental results demonstrate that with regression and classification techniques, it is possible to predict the best garbage collector (along with the minimum possible heap size) with reasonable accuracy given an arbitrary input to an application. The exploration opens the opportunities for tailoring the selection of garbage collectors to not only applications but also their inputs. DA - 2009/7/31/ PY - 2009/7/31/ DO - 10.1145/1618525.1618531 VL - 43 IS - 3 SP - 48 J2 - SIGOPS Oper. Syst. Rev. LA - en OP - SN - 0163-5980 UR - http://dx.doi.org/10.1145/1618525.1618531 DB - Crossref ER - TY - JOUR TI - Program locality analysis using reuse distance AU - Zhong, Yutao AU - Shen, Xipeng AU - Ding, Chen T2 - ACM Transactions on Programming Languages and Systems AB - On modern computer systems, the memory performance of an application depends on its locality. For a single execution, locality-correlated measures like average miss rate or working-set size have long been analyzed using reuse distance —the number of distinct locations accessed between consecutive accesses to a given location. This article addresses the analysis problem at the program level, where the size of data and the locality of execution may change significantly depending on the input. The article presents two techniques that predict how the locality of a program changes with its input. The first is approximate reuse-distance measurement, which is asymptotically faster than exact methods while providing a guaranteed precision. The second is statistical prediction of locality in all executions of a program based on the analysis of a few executions. The prediction process has three steps: dividing data accesses into groups, finding the access patterns in each group, and building parameterized models. The resulting prediction may be used on-line with the help of distance-based sampling. When evaluated on fifteen benchmark applications, the new techniques predicted program locality with good accuracy, even for test executions that are orders of magnitude larger than the training executions. The two techniques are among the first to enable quantitative analysis of whole-program locality in general sequential code. These findings form the basis for a unified understanding of program locality and its many facets. Concluding sections of the article present a taxonomy of related literature along five dimensions of locality and discuss the role of reuse distance in performance modeling, program optimization, cache and virtual memory management, and network traffic analysis. DA - 2009/8/1/ PY - 2009/8/1/ DO - 10.1145/1552309.1552310 VL - 31 IS - 6 SP - 1-39 J2 - ACM Trans. Program. Lang. Syst. LA - en OP - SN - 0164-0925 UR - http://dx.doi.org/10.1145/1552309.1552310 DB - Crossref KW - Measurement KW - Languages KW - Algorithms KW - Program locality KW - reuse distance KW - stack distance KW - training-based analysis ER - TY - CONF TI - Cross-Input Learning and Discriminative Prediction in Evolvable Virtual Machines AU - Mao, Feng AU - Shen, Xipeng T2 - 2009 7th Annual IEEE/ACM International Symposium on Code Generation and Optimization (CGO) AB - Modern languages like Java and C# rely on dynamic optimizations in virtual machines for better performance. Current dynamic optimizations are reactive. Their performance is constrained by the dependence on runtime sampling and the partial knowledge of the execution. This work tackles the problems by developing a set of techniques that make a virtual machine evolve across production runs. The virtual machine incrementally learns the relation between program inputs and optimization strategies so that it proactively predicts the optimizations suitable for a new run. The prediction is discriminative, guarded by confidence measurement through dynamic self-evaluation. We employ an enriched extensible specification language to resolve the complexities in program inputs. These techniques, implemented in Jikes RVM, produce significant performance improvement on a set of Java applications. C2 - 2009/3// C3 - 2009 International Symposium on Code Generation and Optimization DA - 2009/3// DO - 10.1109/cgo.2009.10 PB - IEEE SN - 9780769535760 UR - http://dx.doi.org/10.1109/cgo.2009.10 DB - Crossref KW - Cross-Input Learning KW - Java Virtual Machine KW - Evolvable Computing KW - Adaptive Optimization KW - Input-Centric Optimization KW - Discriminative Prediction ER - TY - CONF TI - Speculation with Little Wasting: Saving Cost in Software Speculation through Transparent Learning AU - Jiang, Yunlian AU - Mao, Feng AU - Shen, Xipeng T2 - 2009 15th International Conference on Parallel and Distributed Systems AB - Software speculation has shown promise in parallelizing programs with coarse-grained dynamic parallelism. However, most speculation systems use offline profiling for the selection of speculative regions. The mismatch with the input-sensitivity of dynamic parallelism may result in large numbers of speculation failures in many applications. Although with certain protection, the failed speculations may not hurt the basic efficiency of the application, the wasted computing resource (e.g. CPU time and power consumption) may severely degrade system throughput and efficiency. The importance of this issue continuously increases with the advent of multicore and parallelization in portable devices and multiprogramming environments. In this work, we propose the use of transparent statistical learning to make speculation cross-input adaptive. Across production runs of an application, the technique recognizes the patterns of the profitability of the speculative regions in the application and the relation between the profitability and program inputs. On a new run, the profitability of the regions are predicted accordingly and the speculations are switched on and off adaptively. The technique differs from previous techniques in that it requires no explicit training, but is able to adapt to changes in program inputs. It is applicable to both loop-level and function-level parallelism by learning across iterations and executions, permitting arbitrary depth of speculations. Its implementation in a recent software speculation system, namely the behavior-oriented parallelization system, shows substantial reduction of speculation cost with negligible decrease (sometimes, considerable increase) of parallel execution performance. C2 - 2009/// C3 - 2009 15th International Conference on Parallel and Distributed Systems DA - 2009/// DO - 10.1109/ICPADS.2009.130 PB - IEEE SN - 9781424457885 UR - http://dx.doi.org/10.1109/ICPADS.2009.130 DB - Crossref ER - TY - JOUR TI - Response to Ezell and von Winterfeldt AU - Parnell, G.S. AU - Borio, L.L. AU - Cox, L.A. AU - Brown, G.G. AU - Pollock, S. AU - Wilson, A.G. T2 - Biosecurity and Bioterrorism AB - Biosecurity and Bioterrorism: Biodefense Strategy, Practice, and ScienceVol. 7, No. 1 CommentaryResponse to Ezell and von WinterfeldtGregory S. Parnell, Luciana L. Borio, Louis A. (Tony) Cox, Gerald G. Brown, Stephen Pollock, and Alyson G. WilsonGregory S. ParnellSearch for more papers by this author, Luciana L. BorioSearch for more papers by this author, Louis A. (Tony) CoxSearch for more papers by this author, Gerald G. BrownSearch for more papers by this author, Stephen PollockSearch for more papers by this author, and Alyson G. WilsonSearch for more papers by this authorPublished Online:20 Apr 2009https://doi.org/10.1089/bsp.2009.0927AboutSectionsPDF/EPUB Permissions & CitationsPermissionsDownload CitationsTrack CitationsAdd to favorites Back To Publication ShareShare onFacebookTwitterLinked InRedditEmail "Response to Ezell and von Winterfeldt." , 7(1), pp. 111–112FiguresReferencesRelatedDetailsCited byIs ALARP applicable to the management of terrorist risks?Reliability Engineering & System Safety, Vol. 95, No. 8 Volume 7Issue 1Mar 2009 InformationMary Ann Liebert, Inc.To cite this article:Gregory S. Parnell, Luciana L. Borio, Louis A. (Tony) Cox, Gerald G. Brown, Stephen Pollock, and Alyson G. Wilson.Response to Ezell and von Winterfeldt.Biosecurity and Bioterrorism: Biodefense Strategy, Practice, and Science.Mar 2009.111-112.http://doi.org/10.1089/bsp.2009.0927Published in Volume: 7 Issue 1: April 20, 2009PDF download DA - 2009/// PY - 2009/// DO - 10.1089/bsp.2009.0927 VL - 7 IS - 1 SP - 111-112 UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-65349093369&partnerID=MN8TOARS ER - TY - JOUR TI - Probability, chance and the probability of chance AU - Singpurwalla, N.D. AU - Wilson, A.G. T2 - IIE Transactions (Institute of Industrial Engineers) AB - In our day-to-day discourse on uncertainty, words like belief, chance, plausible, likelihood and probability are commonly encountered. Often, these words are used interchangeably, because they are intended to encapsulate some loosely articulated notions about the unknowns. The purpose of this paper is to propose a framework that is able to show how each of these terms can be made precise, so that each reflects a distinct meaning. To construct our framework, we use a basic scenario upon which caveats are introduced. Each caveat motivates us to bring in one or more of the above notions. The scenario considered here is very basic; it arises in both the biomedical context of survival analysis and the industrial context of engineering reliability. This paper is expository and much of what is said here has been said before. However, the manner in which we introduce the material via a hierarchy of caveats that could arise in practice, namely our proposed framework, is the novel aspect of this paper. To appreciate all this, we require of the reader a knowledge of the calculus of probability. However, in order to make our distinctions transparent, probability has to be interpreted subjectively, not as an objective relative frequency. DA - 2009/// PY - 2009/// DO - 10.1080/07408170802322630 VL - 41 IS - 1 SP - 12-22 UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-56849107795&partnerID=MN8TOARS KW - Belief functions KW - biometry KW - likelihood KW - plausibility KW - quality assurance KW - reliability KW - survival analysis KW - uncertainty KW - vagueness ER -