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)

百度搜索“yundocx”或“云文档网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，云文档网，提供经典知识文库A Framework for Automatic Adaptation of Tunable Distributed在线全文阅读。