A Framework for Automatic Adaptation of Tunable Distributed

Automatic Adaptation of Tunable Distributed Applications

by

Fangzhe Chang

A dissertation submitted in partial ful?llment

of the requirements for the degree of

Doctor of Philosophy

Department of Computer Science

New York University

January2001

Research Advisors:

Vijay Karamcheti

c Fangzhe Chang

All Rights Reserved,2001

To my family for their support in all these years

iii

Acknowledgment

I am indebted to my family,which have given me strong support in all these years to pursue my own ambition.Special thanks to my advisors:Zvi M.Kedem and Vijay Karamcheti.It is from Zvi that I learned to appreciate simplicity and to look for inter-esting problems from ordinary tasks in the computer world.It is Vijay who showed me how to partition problems,write papers,give presentations,and keep extending current work for further goals and development.

I have been working in a very good team.I had enormous help from Ayal Itzkovitz, Arash Baratloo,Tao Zhao,Ninghui Li,Xiaodong Fu,Anatoly Akkerman,Ting-jen Yen,Ee-Chien Chang,Naftali Schwartz,and Hiroshi Ishikawa in my project.I en-joyed discussions and help from all those people:Hseu-Ming Chen,Allen Leung,Karl Holger,Weisong Shi,Mehmet Karaul,Yuanyuan Zhao,Hua Wang,Ilya Lipkind,Anca-Andreea Ivan,Gediminas Adomavicius,Deepak Goyal,Chen Li,Xianghui Duan,Zhe Yang,Fabian Monrose,Peter Piatko,Churngwei Chu,Peter Wyckoff,Niranjan Ni-lakantan,Madhu Nayakkankuppam,and Shih-Chen Huang.Many thanks to all of them.

This research was sponsored by the Defense Advanced Research Projects Agency under agreement numbers F30602-96-1-0320,F30602-99-1-0157,and N66001-00-1-8920;by the National Science Foundation under CAREER award number CCR–9876128 and grant number CCR-9988176;and Microsoft.The 6a9caf1455270722192ef798ernment is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copy-

iv

right annotation thereon.The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the of?cial policies or endorsements,either expressed or implied,of the Defense Advanced Research Projects Agency,Rome Laboratory,SPAW AR SYSCEN,or the 6a9caf1455270722192ef798ernment.

v

Abstract

Current-day applications are written to execute on a wide range of platforms rang-ing from fast desktop computers to mobile laptops all the way to hand-held PDAs and cellular phones,spanning several orders of magnitude in processing,storage,and com-munication capabilities.Applications running on these platforms may exhibit perse and unpredictable performance because of platform heterogeneity and varying resource availability,resulting from competition with other applications or from migration of applications themselves to a different execution environment.However,application users typically expect a desired level of Quality of Service(QoS),either in terms of performance optimization(e.g.,shortest completion time)or in terms of predictabil-ity(e.g.,bounded completion time).This motivates development of resource-aware applications,which proactively monitor and control their utilization of the underlying platform,and ensure a desired performance level by adapting themselves to changing resource characteristics.

In this dissertation,we describe an application-independent adaptation framework that simpli?es the design of resource-aware applications.This framework eliminates the need for adaptation decisions to be explicitly programmed into applications by re-lying on three components:(1)a tunability interface,which exposes adaptation choices in the form of alternate application con?gurations while encapsulating core application functionality;(2)a virtual execution environment,which emulates application execu-tion under perse resource availability enabling off-line collection of information about resulting behavior;and(3)run-time adaptation agents,which permit monitoring and steering of the application execution.Together,these components permit automatic

vi

run-time decisions on when to adapt the application behavior by continuously moni-toring resource conditions and application progress,and how to adapt by dynamically choosing an application con?guration most appropriate for the prescribed user prefer-ences.

We evaluate the framework using a distributed image visualization application and a parallel image processing application.The framework permits automatic adaptation to changes of execution environment characteristics such as network bandwidth and image arrival pattern by switching application con?gurations to satisfy user preferences for output quality and execution timeliness.

vii

Contents

Dedication iii

Acknowledgment iv Abstract vi List of Figures xii

1Introduction1

1.1Motivation (1)

1.2Application Adaptation (3)

1.3Approach (6)

1.4Contributions (7)

1.5Organization (7)

2Background9

2.1Application Structure (9)

2.2Adaptation for Performance (11)

2.3Related Work (13)

2.4Our Model (17)

viii

3An Adaptation Framework for Tunable Applications23

3.1Application Tunability (23)

3.2Adaptation Framework (27)

4Tunability Interface30

4.1Application Structuring Constructs (32)

4.2Application Monitoring and Control Constructs (34)

4.3Source-level Implementation of Tunability Interface (36)

4.4Binary-level Realization of Tunability Interface (41)

4.5Summary (45)

5Virtual Execution Environment46

5.1Construction of Virtual Execution Environment (48)

5.1.1General Strategy (49)

5.1.2Implementation on Windows NT (54)

5.1.3Differences in Linux implementation (62)

5.2Obtaining Application Performance Pro?les (64)

5.3Summary (67)

6Run-time Adaptation System68

6.1Monitoring Agent (69)

6.2Steering Agent (73)

6.3Resource Scheduler (73)

6.4Summary (76)

7Bene?ts of Tunable Applications78

ix

7.1Scheduling Formulation (79)

7.2A Parameterizable Task System (81)

7.3Tunability Bene?ts for Non-malleable Tasks (82)

7.4Tunability Bene?ts for Malleable Tasks (86)

7.5Summary (89)

8Case Study:Active Visualization92

8.1Application Structure (92)

8.2Tunability of Active Visualization (94)

8.3Application Annotation (95)

8.4Application Pro?le (102)

8.5Evaluation of the Framework (104)

8.6Summary (110)

9Case Study:Junction Detection112

9.1Application Structure (113)

9.1.1Calypso System (113)

9.1.2Junction Detection Application (115)

9.2Tunability of Junction Detection (116)

9.3Application Annotation (118)

9.4Application Pro?le (123)

9.5Evaluation of the Framework (125)

9.6Summary (130)

10Concluding Remarks131

10.1Summary of This Dissertation (131)

x

10.2Conclusion (133)

10.3Future Work (134)

10.4Perspective (136)

Bibliography139

xi

List of Figures

3.1Application con?guration and adaptation framework (29)

5.1Ideal control of CPU shares (51)

5.2Strategy for control of physical memory (53)

5.3Strategy for control of CPU resource (57)

5.4CPU usage snapshot (58)

5.5Control of memory usage (61)

5.6Control of network Usage (63)

5.7Using sandbox to simulate physical machines (65)

5.8A simple form of performance database (67)

6.1Run-time components (69)

6.2Monitoring agent’s view of CPU resource availability (71)

6.3Monitoring of network resource availability (72)

6.4Specifying user preferences in QoS constraints (75)

7.1A parameterizable tunable job (81)

7.2Performance impact of tunability for non-malleable jobs (84)

7.3Performance impact of tunability for malleable jobs (88)

xii

7.4Impact of tunability in non-malleable mode and malleable model (90)

8.1Structure of Active Visualization application (93)

8.2Structure of the original client side program of Active Visualization (94)

8.3Tunability parameters for Active Visualization (97)

8.4Tunability annotation of Active Visualization (98)

8.5New de?nition for the intercepted function (101)

8.6Annotation of intercepted functions (101)

8.7Pro?ling Active Visualization for different CPU conditions (102)

8.8Pro?ling Active Visualization for different network conditions (103)

8.9Adapting compression method to changes in network conditions (106)

8.10Adapting image resolution to changes in CPU conditions (107)

8.11Adapting fovea size to changes in CPU conditions (108)

9.1A fragment of an evolving Calypso computation (114)

9.2Structure of the parallel Junction Detection application (116)

9.3Original Calypso code of Junction Detection (117)

9.4Tunability parameters for Junction Detection (119)

9.5Tunability annotation of Junction Detection (120)

9.6Pro?ling Junction Detection application (124)

9.7Adapting sampling scheme to characteristics of input data (127)

9.8Adapting machine allocation scheme to image arrival pattern (128)

xiii

Chapter1

Introduction

1.1Motivation

Current-day applications are written to execute on a wide range of platforms rang-ing from fast desktop computers,mobile laptops,all the way to hand-held Personal-Digital-Assistants(PDAs),cellular phones,and PC watches,spanning several orders of magnitude in processing,storage,and communication capabilities,and differing in the system support for application execution.Current desktop machines can have mul-tiple gigahertz(GHz)processors,a gigabytes(GB)of memory,a hundred GB of hard disk,and gigabits-per-second(Gbps)network 6a9caf1455270722192ef798ptop machines are typically less powerful due to constraints on their size,weight,and battery life,with a single CPU,less memory,smaller hard disk,and lower bandwidth network connectivity.The power of PDAs is further limited:A Palm V only has a16MHz CPU(Motorola68328) and2megabytes(MB)of memory.These lower-end devices could be connected using infra-red,wireless,and bluetooth[32]facilities;thus achieving different rates of data transmission.

1

With the trend of“write once,run everywhere”software,more and more applica-tions are able to execute on these heterogeneous platforms or even migrate from one platform to another at run time.For instance,Microsoft provides Win32Application Programming Interface(API)for all its Windows platforms such as Windows NT[55] on desktop machines and or Windows CE[6]on hand-held PDAs(although Windows CE only implements a subset of APIs supported by Windows NT).Applications written using Win32API can potentially execute on both desktops and PDAs running Microsoft operating systems.With the popularity of virtual machines as execution platforms(e.g., the Java virtual machine(JVM)[47]or the 6a9caf1455270722192ef798 platform[56]),it is possible for the same application to execute on heterogeneous devices with different OSes.For example,a Java application may be able to run on both Palm Pilot PDAs with PalmOS and desktop machines with the Windows NT operating system,even though the K Vir-tual Machine(KVM)[59]on the former is only a core subset of a full-featured JVM running on the latter.

However,these applications may exhibit perse and unpredictable performance due to heterogeneous power of physical platforms in processing,storage,and communica-tion capabilities,as well as to dynamically varying resource availability resulting from competition with other applications or migration of(parts of)applications to a different execution environment[50].

However,such widely varying performance is at odds with the expectations of ap-plication users who typically expect a desired level of Quality of Service(QoS).For example,a user viewing a large image over the network may expect that the response time be reasonable.Because this cannot be met on all platforms for a high resolution image,we take advantage of the fact that the user’s expectation are not absolute—there

2

is some?exibility in expressing his expectations:he may prefer a detailed map when using a powerful desktop computer with a high bandwidth network link;however,he may prefer responsiveness at the cost of a lower resolution when using a connected hand-held device with a thin network link.

However,taking advantage of this?exibility in user expectations requires the ability to express user preferences as well as applications’capability to deliver these prefer-ences despite different execution scenarios.More generally,this motivates the design of resource-aware applications,which proactively monitor and control its execution and utilization of the underlying platform,can ensure a desired performance level by adapting themselves to changing resource characteristics.For instance,a distributed application conveying a video stream from a server to a client can respond to a reduc-tion in available network bandwidth by compressing the stream or selectively dropping frames.In other words,applications need to be aware of alternate ways to execute as well as the execution environment,and dynamically select an appropriate behavior to adapt to changes of resource availability and satisfy user preferences.These alter-nate ways to execute could be statically programmed,or dynamically generated and injected into executing applications.In essence,they correspond to different execution paths and provide tradeoff among resource requirements,application performance,and even functionality.

1.2Application Adaptation

An application may have multiple forms that suit different execution scenarios.In the application source code,these multiple execution forms may take different algorithms to achieve the same functionality,different settings for the same algorithm,or consists

3

of different modules for add-on and more re?ned computation.At run time,these multiple forms present?exible ways of execution,resulting in different execution path and more importantly different resource requirements and performance levels.The various ways of execution at run time can be viewed as different con?gurations that could be selected based on the changes of resource conditions.

The importance of adapting application behavior to the run-time scenarios such as resource conditions or external events has been understood for a long time.The traditional way to enable adaptation is to explicitly program it into applications.For instance,the TCP protocol responds to network congestion by adaptively deciding an appropriate size of the sliding window and a timeout period for retransmission.Current TCP implementations have been highly optimized for transmitting a large amount of data.However,the drawback with such an approach is that they presuppose all possible patterns of usage.Optimizations based on these assumed usage patterns may not work well for other scenarios.For instance,it has been shown[8]that the default con?gura-tion for TCP yields unnecessary delays for short HTTP request/reply traf?c(that could be avoided by a speci?c setting of socket options).Also,TCP resizing protocols have been shown to be poorly suited to high bandwidth transmission in Wide Area Network (W AN)environment[24].

Although adaptation has been programmed into various applications,little support is available for structuring general-purpose resource-aware applications.Several re-search projects have begun to address this shortcoming[17,44,46,52,57,51];how-ever,most such efforts place a substantial burden on application developers requiring them to provide explicit speci?cation of both resource-utilization pro?les(which re-sources are used at which time and in what quantity),and adaptation behaviors(how

4

applications react to changes in resource conditions).

More robust application adaptation is possible if programmers only identify what the alternate con?gurations are,leaving it up to the run-time system to automatically select an appropriate con?guration based on execution environments.We focuses on how to enable the development of adaptive applications without these adaptation de-cisions to be explicitly programmed;thus simplifying the development and supporting more?exible adaptation policies.

We observe that many parallel and distributed applications contain parameters(i.e., variables)that have multiple reasonable(schemes of)settings,such as the value of timeout for retransmission in TCP.The particular setting or scheme adopted are usually optimized for an expected run-time environment.However,in today’s platforms of ever-increasing heterogeneity,the adopted form may not work well in all environments; attesting the need for multiple con?gurations of applications.

We study the performance bene?t of automatic application adaptation from mul-tiple application con?gurations in parallel and distributed environments,in particular focusing upon answers to the following questions:

1.what are con?gurations of an application?

2.how to specify application con?gurations?

3.how to evaluate the performance of these application con?gurations?

4.how to monitor the resource availability of the execution environment?

5.how to dynamically select the appropriate application con?guration based on

changes of resource availability at run time?

6.what are the performance bene?ts of multiple application con?gurations?

The answers to these questions allow us to devise mechanisms to expose different

5

con?gurations of applications and dynamically choose the appropriate con?guration to adapt to changes of execution environment such as resource availability,or in a more general form,occurrences of some speci?c events.These mechanisms in turn can avoid the explicit programming of adaptation decisions into applications.

1.3Approach

We assume applications of interest already contain?exibility in their implementation, although they may be?xed to one con?guration by default.The execution?exibility is controlled by some control“knobs”,different settings of which correspond to different con?gurations.However,these control knobs are typically implicit in the program.We abstract different con?gurations out by promoting these implicit parameters to appli-cation control structures that can be manipulated from outside of applications.Thus, application adaptation is the switching from one con?guration to another con?guration by manipulating the explicit control structures,with decisions made and enforced by system components other than applications themselves.However,to make appropriate adaptation decisions,it is necessary to know the performance levels of all the appli-cation con?gurations as well as the current execution conditions,requiring an entire infrastructure collaborating together to delivered user-preferred performance levels.In this dissertation,we construct a framework that exposes con?gurations of arbitrary ap-plications,evaluates their performance,and dynamically switches among them to adapt to changing execution environments.

6

1.4Contributions

This dissertation proposes,from the point of view of resource management,the notion of application tunability as an abstraction for multiple application con?gurations,and studies the bene?t of application tunability.It presents a framework for the automatic adaptation of tunable applications,including language annotations that add tunabil-ity interfaces to traditional applications,a virtual execution environment that permits modeling of application behavior under various resource conditions,and run-time com-ponents that monitor resource availability and automatically adapt applications for a desired level of service.It evaluates this framework with two example applications:a parallel image processing application called Junction Detection[38]and a distributed visualization application called Active Visualization[11].

1.5Organization

Chapter2introduces the project background and the notion of tunability,and discusses related work.Chapter3proposes a general framework for enabling automatic adap-tation of tunable applications in response to external changes.Chapter4studies the tunability interface:the language annotations that expose alternate con?gurations of applications,enabling run-time monitoring and control of application execution.Chap-ter5presents the design and implementation of a virtual execution environment that simulates various resource conditions,and describes its use for modeling application behavior.Chapter6describes the run-time components that monitor execution envi-ronment and steer application execution to adapt to changes of resource conditions. Chapter7evaluates the bene?t of tunable applications,using simulation to show how

7

tunability can help achieving better system-wide resource utilization.Chapter8and Chapter9present two case studies,using a parallel image processing application and distributed visualization application.Finally,Chapter10concludes and discusses fu-ture work.

8

本文来源：https://www.bwwdw.com/article/1bal.html