FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 |

«Abstract. Despite claims of “embarrassing parallelism” for many opti- misation algorithms, there has been very little work on exploiting par- ...»

-- [ Page 1 ] --

Highly Scalable Multi Objective Test Suite

Minimisation Using Graphics Cards

Shin Yoo1 Mark Harman1 and Shmuel Ur2


University College London


University of Bristol

Abstract. Despite claims of “embarrassing parallelism” for many opti-

misation algorithms, there has been very little work on exploiting par-

allelism as a route for SBSE scalability. This is an important oversight

because scalability is so often a critical success factor for Software Engi-

neering work. This paper shows how relatively inexpensive General Pur- pose computing on Graphical Processing Units (GPGPU) can be used to run suitably adapted optimisation algorithms, opening up the possibility of cheap scalability. The paper develops a search based optimisation ap- proach for multi objective regression test optimisation, evaluating it on benchmark problems as well as larger real world problems. The results indicate that speed–ups of over 25x are possible using widely available standard GPUs. It is also encouraging that the results reveal a statisti- cally strong correlation between larger problem instances and the degree of speed up achieved. This is the first time that GPGPU has been used for SBSE scalability.

1 Introduction There is a pressing need for scalable solutions to Software Engineering problems.

This applies to SBSE work just as much as it does to other aspects of Software Engineering. Scalability is widely regarded as one of the key problems for Soft- ware Engineering research and development [1, 2]. Furthermore, throughout its history, lack of scalability has been cited as an important barrier to wider uptake of Software Engineering research [3–5]. Without scalable solutions, potentially valuable Software Engineering innovations may not be fully exploited.

Many search based optimisation techniques, such as evolutionary algorithms are classified as ‘embarrassingly parallel’ because of their potential for scalability through parallel execution of fitness computations [6]. However, this possibility for significant speed–up (and consequent scalability) has been largely overlooked in the SBSE literature. The first authors to suggest the exploitation of parallel ex- ecution were Mitchell et al. [7] who used a distributed architecture to parallelise modularisation through the application of search-based clustering. Subsequently, Mahdavi et al. [8] used a cluster of standard PCs to implement a parallel hill climbing algorithm. More recently, Asadi et al. [9] used a distributed architecture to parallelise a genetic algorithm for the concept location problem.

Of 763 papers on SBSE [10] only these three present results for parallel execution of SBSE. Given the ‘embarrassingly parallel’ natureof the underlying approach and the need for scalability, it is perhaps surprising that there has not been more work on SBSE parallelisation. One possible historical barrier to wider application of parallel execution has been the high cost of parallel execution architectures and infrastructure. All three previous results cited in the previous paragraph used a cluster of machines to achieve parallelism. While commodity PCs have significantly reduced the cost of such clusters, their management can still be a non-trivial task, restricting the potential availability for developers.

Fortunately, recent work [11] has shown how a newly emerging parallelism, originally designed for graphics, can be exploited for non–graphical tasks using General Purpose computing on Graphical Processing Unit (GPGPU) [12]. Modern graphics hardware provides an affordable means of parallelism: not only the hardware is more affordable than multiple PCs but also the management cost is much smaller than that required for a cluster of PCs because it depends on a single hardware component. GPGPU has been successfully applied to various scientific computations [13, 14]. However, these techniques have never been applied to Search-Based Software Engineering problems and so it remains open as to whether large-scale, affordable speed–up is possible for Software Engineering optimisations using GPGPU to parallelise SBSE.

Fast regression test minimisation is an important problem for practical software testers, particularly where large volumes of testing are required on a tight build schedule. For instance, the IBM middleware product used as one of the systems in the empirical study in this paper is a case in point. While it takes over four hours to execute the entire test suite for this system, the typical smoke test scenario performed after each code submit is assigned only an hour or less of testing time, forcing the tester to select a subset of tests from the available pool.

If the computation involved in test suite minimisation requires more than one hour itself, then the tester cannot benefit from such a technique; the smoke test will be highly suboptimal as a result. Using the GPGPU approach introduced in this paper, this time was reduced from over an hour to just under 3 minutes, thereby allowing sophisticated minimisation to be used on standard machines without compromising the overall build cycle.

The paper presents a modified evolutionary algorithm for the multi-objective regression test minimisation problem. The algorithm is modified to support implementation on a GPU by transforming the fitness evaluation of the population of individual solutions into a matrix-multiplication problem, which is inherently parallel and renders itself very favourably to the GPGPU approach. This transformation to matrix-multiplication is entirely straightforward and may well be applicable to other SBSE problems, allowing them to benefit from similar scaleups to those reported in this paper.

This algorithm has been implemented using OpenCL technology, a framework for GPGPU. The paper reports the results of the application of the parallelised GPGPU algorithm on 13 real world programs, including widely studied, but relatively small examples from the Siemens’ suite [15], through larger more realistic real world examples from the Software-Infrastructure Repository (SIR) for testing [16], and on a very large IBM middleware regression testing problem.

The primary contributions of the paper are as follows:

1. The paper is the first to develop SBSE algorithms for GPGPU as a mechanism for affordable massive parallelism.

2. The paper presents results for real world instances of the multi objective test suite minimisation problem. The results indicate that dramatic speed– up is achievable. For the systems used in the empirical study, speed–ups over 20x were observed. The empirical evidence suggests that, for larger problems where the scale up is the most needed, the degree of speed–up is the most dramatic; a problem that takes over an hour using conventional techniques, can be solved in minutes using the GPGPU approach. This has important practical ramifications because regression testing cycles are often compressed: overnight build cycles are not uncommon.

3. The paper studies multiple evolutionary algorithms and both GPU- and CPU-based parallelisation methods in order to provide robust empirical evidence for the scalability conferred by the use of GPGPU. The GPGPU parallelisation technique maintained the same level of speed–up across all algorithms studied. The empirical evidence highlights the limitations of CPUbased parallelisation: with smaller problems, multi-threading overheads erode the speed–up, whereas with larger problems it fails to scale as well as GPUbased parallelisation.

4. The paper explores the factors that influence the degree of speed–up achieved, revealing that both program size and test suite size are closely correlated to the degree of speed–up achieved. The data have a good fit to a model for which increases in the degree of scale up achieved are logarithmic in both program and test suite size.

The rest of the paper is organised as follows. Section 2 presents background and related work in test suite minimisation and GPGPU-based evolutionary computation. Section 3 describes how the test suite minimisation problem is re-formulated for a parallel algorithm, which is described in detail in Section 4.

Section 5 describes the details of the empirical study, the results of which are analysed in Section 6. Section 7 discusses the related work and Section 8 concludes.

2 Background

Multi-Objective Test Suite Minimisation: The need for test suite minimisation arises when the regression test suite of an existing software system grows to such an extent that it may no longer be feasible to execute the entire test suite [17]. In order to reduce the size of the test suite, any redundant test cases in the test suite need to be identified and removed. More formally, test suite

minimisation problem can be defined as follows [18]:

Test Suite Minimisation Problem Given: A test suite of m tests, T, a set of l test goals R = {r1,..., rl }, that must be satisfied to provide the desired ‘adequate’ testing of the program, and subsets of T, Ti s, one associated with each of the ri s such that any one of the test cases tj belonging to Ti can be used to achieve requirement ri.

Problem: Find a representative set, T, of test cases from T that satisfies R.

The testing criterion is satisfied when every test-case requirement in R is satisfied. A test-case requirement, ri, is satisfied by any test case, tj, that belongs to Ti, a subset of T. Therefore, the representative set of test cases is the hitting set of Ti s. Furthermore, in order to maximise the effect of minimisation, T should be the minimal hitting set of Ti s. The minimal hitting-set problem is an NPcomplete problem as is the dual problem of the minimal set cover problem [19].

The NP-hardness of the problem encouraged the use of heuristics and metaheuristics. The greedy approach [20] as well as other heuristics for minimal hitting set and set cover problem [21, 22] have been applied to test suite minimisation but these approaches were not cost-cognisant and only dealt with a single objective (test coverage). With the single-objective problem formulation, the solution to the test suite minimisation problem is one subset of test cases that maximises the test coverage with minimum redundancy.

Since the greedy algorithm does not cope with multiple objectives very well, Multi-Objective Evolutionary Algorithms have been applied to the multiobjective formulation of the test suite minimisation [23, 24]. While this paper studies three selected MOEAs, the principle of parallelising fitness evaluation of multiple solutions in the population of an MOEA applies universally to any MOEA.

GPGPU and Evolutionary Algorithms: Graphics cards have become a compelling platform for intensive computation, with a set of resource-hungry graphic manipulation problems that have driven the rapid advances in their performance and programmability [12]. As a result, consumer-level graphics cards boast tremendous memory bandwidth and computational power. For example, ATI Radeon HD4850 (the graphics card used in the empirical study in the paper), costing about $150 as of April 2010, provides 1000GFlops processing rate and

63.6GB/s memory bandwidth. Graphics cards are also becoming faster more quickly compared to CPUs. In general, it has been reported that the computational capabilities of graphics cards, measured by metrics of graphics performance, have compounded at the average yearly rate of 1.7x (rendered pixels/s) to

2.3x (rendered vertices/s) [12]. This significantly outperforms the growth in traditional microprocessors; using the SPEC benchmark, the yearly rate of growth for CPU performance has been measured at 1.4x by a recent survey [25].

The disparity between two platforms is caused by the different architecture.

CPUs are optimised for executing sequential code, whereas GPUs are optimised for executing the same instruction (the graphics shader) with data parallelism (different objects on the screen). This Single-Instruction/Multiple-Data (SIMD) architecture facilitates hardware-controlled massive data parallelism, which results in the higher performance.

It is precisely this massive data-parallelism of General-Purpose computing on Graphics Processing Units (GPGPU) that presents GPGPU as an ideal platform for parallel evolutionary algorithms. Many of these algorithms require the calculation of fitness (single instruction) for multiple individual solutions in the population pool (multiple data). Early work has exploited this potential for parallelism with both single- and multi-objective evolutionary algorithms [26–28].

However, most existing evaluation has been performed on benchmark problems rather than practical applications.

3 Parallel Formulation of MOEA Test Suite Minimisation Parallel Fitness Evaluation: The paper considers, for parallelisation, a multi objective test suite minimisation problem from existing work [24]. In order to parallelise test suite minimisation, the fitness evaluation of a generation of individual solutions for the test suite minimisation problem is re-formulated as a matrix multiplication problem. Instead of computing the two objectives (i.e. coverage of test goals and execution cost) for each individual solution, the solutions in the entire population are represented as a matrix, which in turn is multiplied by another matrix that represents the trace data of the entire test suite.

The result is a matrix that contains information for both test goal coverage and execution cost. While the paper considers structural coverage as test goal, the proposed approach is equally applicable to other testing criteria, such as dataow coverage and functional coverage provided that there is a clear mapping between tests and the test objectives they achieve.

More formally, let matrix A contain the trace data that capture the test goals achieved by each test; the number of rows of A equals the number of test goals to be covered, l, and the number of columns of A equals the number of test cases in the test suite, m. Entry ai,j of A stores 1 if the test goal fi was executed (i.e.

covered) by test case tj, 0 otherwise.

The multiplier matrix, B, is a representation of the current population of individual solutions that are being considered by a given MOEA. Let B be an m-by-n matrix, where n is the size of population for the given MOEA. Entry bj,k of B stores 1 if test case tj is selected by the individual pk, 0 otherwise.

Pages:   || 2 | 3 |

Similar works:

«Separating the Hope from the Hype: More perspectives on the use of information and communication technologies (ICTs) to benefit education in developing countries Excerpts from the World Bank’s EduTech blog (Volume III) Michael Trucano The World Bank 2012 Separating the Hope from the Hype: More perspectives on the use of information and communication technologies (ICTs) to benefit education in developing countries Excerpts from the World Bank’s EduTech blog Michael Trucano The World Bank...»

«Klagenævnet for Udbud J.nr.: 2016-5734 (Kirsten Thorup, Lene Ravnholt) 14. oktober 2016 KENDELSE Axiell Danmark A/S (advokat David Salomonsen, Hellerup) mod Lyngby-Taarbæk Kommune (advokat Anders Birkelund Nielsen, København) Ved udbudsbekendtgørelse nr. 2016/S 087-153173 af 29. april 2016 udbød Lyngby-Taarbæk Kommune som offentligt udbud efter udbudsloven en kontrakt om køb og installering af sorteringsanlæg til Stadsbiblioteket i Lyngby. Lyngby-Taarbæk Kommune modtog 4 tilbud, heraf...»

«1 INTERNATIONAL PAINFUL BLADDER FOUNDATION Interstitial Cystitis/ Bladder Pain Syndrome Interstitial Cystitis, Bladder Pain Syndrome, Hypersensitive Bladder, Hunner Lesion Chronic Pelvic Pain, Associated Disorders An overview of Diagnosis & Treatment Jane M. Meijlink May 2016 International Painful Bladder Foundation 2014 2 This information brochure is published by the International Painful Bladder Foundation. The International Painful Bladder Foundation is registered at the Chamber of Commerce...»

«MODELING PACKAGED HEAT PUMPS IN A QUASI-STEADY STATE ENERGY SIMULATION PROGRAM By TANG, CHIH CHIEN Bachelor of Science Oklahoma State University, Stillwater, Oklahoma 2003 Submitted to the Faculty of the Graduate College of the Oklahoma State University in partial fulfillment of the requirements for the Degree of MASTER OF SCIENCE May, 2005 MODELING PACKAGED HEAT PUMPS IN A QUASI-STEADY STATE ENERGY SIMULATION PROGRAM Thesis Approved: Dr. Daniel Fisher Thesis Adviser Dr. Jeffrey Spitler Dr. Ron...»

«Experimental investigation of water evaporation from sand and clay using an environmental chamber Weikang Song To cite this version: Weikang Song. Experimental investigation of water evaporation from sand and clay using an environmental chamber. Materials. Universit´ Paris-Est, 2014. English. NNT : e 2014PEST1047. tel-01127303 HAL Id: tel-01127303 https://pastel.archives-ouvertes.fr/tel-01127303 Submitted on 7 Mar 2015 HAL is a multi-disciplinary open access L’archive ouverte...»

«Incredible Years Fostering social and emotional competence: Implementing Dina Dinosaur’s social skills and problem solving curriculum in inclusive early childhood programs Gail E. Joseph, Ph. D. University of Denver 2450 S. Vine Street Ammi Hyde Bldg. #226 Denver, CO 80208 P: 303-871-6466 E: gjoseph2@du.edu Carolyn Webster-Stratton, Ph.D., FAAN Jamila Reid, Ph.D. Parenting Research Clinic Box 357262 University of Washington Seattle, WA 98195-7262 1 Incredible Years Christopher is a very...»

«Explaining stable partnerships among FTMs and MTFs: a significant difference? Frank Lewins School of Social Sciences, Australian National University Abstract Research on male to female (MTFs) and female to male (FTMs) transsexuals has pointed to a number of important differences between these categories, namely their different propensity towards cross dressing and relative levels of mental stability. Recent research demonstrates that these assumed differences are not supported by evidence. One...»

«Minimising and Managing Physical Restraint Safeguarding Processes, Governance Arrangements, and Roles and Responsibilities Contents Introduction 2   Background 2   Purpose 3   Target audience 3   Version update (2015) 3   Chapter 1 – Safeguarding processes 4   Summary of processes 4   1. Training delivery and quality assurance 6   Process description 6   2. Use of MMPR 8   Process description 8   The monitoring and scrutiny of use of force incidents 9   3. Keeping young...»

«Munich Personal RePEc Archive Liquidity Risk and the Credit Crunch of 2007-2009: Evidence from Micro-Level Data on Mortgage Loan Applications Adonis Antoniades 1. July 2013 Online at http://mpra.ub.uni-muenchen.de/49270/ MPRA Paper No. 49270, posted 24. August 2013 11:33 UTC LIQUIDITY RISK AND THE CREDIT CRUNCH OF 2007-2009: EVIDENCE FROM MICRO-LEVEL DATA ON MORTGAGE LOAN APPLICATIONS∗ ADONIS ANTONIADES July 1, 2013 Abstract I test the hypothesis that the banks’ exposure to liquidity risk...»

«Onondaga County Department of Children and Family Services Syracuse/Onondaga County Youth Bureau YOUTH SERVICES DIRECTORY REVISED NOVEMBER 9, 2O16 Revised May 2014 Revised April 2014 Greetings! W e are pleased to present the updated version of the Youth Services Directory. The Syracuse/Onondaga County Youth Bureau, a division of the Onondaga County Department of Children and Family Services, has been publishing the Directory for over 25 years. Our first version had just about half the number of...»

« Putting Hell Back In The Handbasket A Publication of Brazen Church Author Credits: Jacob McMillen, Josiah Pemberton. Julie Ferwerda, Brad Jersak converted by Web2PDFConvert.com  Part 1: A Biblical Staple The Bible Never Even Mentions Hell is not a Biblical concept. Much of the Bible is debatable. Much of the Bible is open to numerous interpretations. There are many theological stances that can be convincingly argued both for AND against. The modern concept of Hell as a place of eternal...»

«LITTLEHAMPTON & DISTRICT WORLD RULES POOL LEAGUE EVERY TEAM MUST TEAM ENTRY FORM COMPLETE THIS FORM Venue Details Venue Name.. Manager/Proprietor Name.. Address...... Telephone.. Email.. General Team Details Team Name.. Captain Vice Captain Name.. Home Address...... Telephone.. Email.. I hereby certify that, I agree that myself and my team will abide by the constitution of the Littlehampton & District World Rules Pool League and adhere to their rules and regulations and that...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.