More Web Proxy on the site http://driver.im/

article

Free access

An algorithm for selection of migration candidates

Authors:

P. WagnerAuthors Info & Claims

ACM SIGMICRO Newsletter, Volume 15, Issue 4

Pages 140 - 146

https://doi.org/10.1145/384281.808224

Published: 01 December 1984 Publication History

Abstract

The NP-Completeness of the selection problem of vertical migration candidates is shown by reducing it to the NP-complete knapsack problem. Based on approximation algorithms for the latter problem a new algorithm is presented, which takes into account the call relations between functions in a complex system. Then the developed algorithm is applied to the UNIX operating system as a representative for complex systems.

References

[1]

G.E. Brown, J.R. Eckhouse, and J. Estabrook, "Operating System Enhancement Through Firmware", Proc. 10th Annual Workshop on Microprogramming, pp. 119-127 (1977).]]

Digital Library

[2]

P. Albrich, "Vertikale Verlagerung - Verfahren, Voraussetzungen, Anwendung", Seminar "Firmware Engineering", Informatik Fachberichte 31, Springer (1980).]]

Digital Library

[3]

P. Meinke, "Verlagerung von Softwarefunktionen in Mikroprogramme", Diplomarbeit am Institut fuer Informatik IV, Universitaet Karlsruhe (1979).]]

[4]

J. Floethe and R.T. Koelsch, "Mikroprogramme als externe PASCAL - Prozeduren", Berichte des German Chapter of the ACM Band 1, B. G. Teubner Verlag, Stuttgart (1979).]]

Digital Library

[5]

J. Stockenberg and A. van Dam, "Vertical Migration for Performance Enhancement in Layered Hardware/Firmware/Software Systems", Computer Mag. 11(5) pp. 35-50 (May 1978).]]

Digital Library

[6]

J.A. Stankovic, "Improving System Structure and its Affect on Vertical Migration", Microprocessing and Microprogramming8(3-5) pp. 203-218 (Oct.-Dec. 1981).]]

[7]

J.A. Stankovic, "The Types and Interactions of Vertical Migration of Functions in a Multi-Level Interpretive System", IEEE Trans. on ComputersC-30(7)(July 1981).]]

Digital Library

[8]

G.E. Brown, J.R. Eckhouse, and Goldberg, "Operating System Enhancement through Microprogramming", SIGMICRO7 pp. 29-33 (March 1976).]]

Digital Library

[9]

E. Luque, A. Ripoll, and J.J. Ruz, "Dynamic Microprogramming in Computer Architecture Redefinition", Euromicro Journal, (6 )pp. 98-103 (1980).]]

[10]

T.G. Rauscher and A.K. Agrawala, "Dynamic Problem Oriented Redefinition of Computer Architecture Via Microprogramming", IEEE Trans. On ComputersC-27 pp. 1006-1014 (1978).]]

Digital Library

[11]

P.S. Liu and F.J. Mowle, "Techniques of Program Execution with a Writable Control Memory", IEEE Transactions On ComputersC-27(9)(Sept 1976).]]

[12]

J. Stankovic, "Good System Structure Features: Their Complexity and Execution Time Cost", IEEE Transactions on Software EngineeringSE-8(4)(July 1982).]]

Digital Library

[13]

J.E. Savage, The Complexity of Computing, J. Wiley & Sons (1976).]]

Digital Library

[14]

S. Sahni, "Approximate Algorithms for the 0/1 Knapsack Problem", Journal ACM22(1) pp. 115-124 (Jan. 1975).]]

Digital Library

[15]

E. Horowitz and S. Sahni, "Computing Partitions with Applications to the Knapsack Problem", Journal ACM21(2) pp. 277-292 (April 1974).]]

Digital Library

[16]

O.H. Ibarra and C.E. Kim, "Fast Approximation Algorithms for the Knappsack and Sum of Subset Problems", JACM22(4) pp. 463-468 (Oct 1975).]]

Digital Library

[17]

B. Holtkamp and H. Kaestner, "A Firmware Monitor to Support Vertical Migration Decisions in the UNIX Operating System", Proc. 15th Annual Workshop on Microprogramming, SIGMICRO Newsletter13(4) pp. 153-162 (December 1982).]]

Digital Library

[18]

P. Wagner, "Vertikale Verlagerung im UNIX-Betriebssystem", Diplomarbeit, Universitaet Dortmund, Abteilung Informatik (1984).]]

[19]

Digital, "PDP- 11/60 Processor Handbook", Digital Equipment Corporation (1977).]]

[20]

Bell, "UNIX Programmer's Manual", Bell Laboratories (January 1979).]]

Cited By

Charlton CLeng PLittle J(1991)Vertical migration of numerical routines in software and microcodeSoftware—Practice & Experience10.1002/spe.438021030521:3(287-297)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.1002/spe.4380210305
Shih L(1990)Microprogramming heritage of RISC design[1990] Proceedings of the 23rd Annual Workshop and Symposium@m_MICRO 23: Microprogramming and Microarchitecture10.1109/MICRO.1990.151454(275-280)Online publication date: 1990
https://doi.org/10.1109/MICRO.1990.151454
Winner R(1988)Naming and Binding in a Vertical Migration EnvironmentIEEE Transactions on Software Engineering10.1109/32.613814:5(599-607)Online publication date: 1-May-1988
https://dl.acm.org/doi/10.1109/32.6138
Show More Cited By

Index Terms

An algorithm for selection of migration candidates
1. Software and its engineering
  1. Software organization and properties
    1. Contextual software domains
      1. Operating systems
2. Theory of computation
  1. Computational complexity and cryptography
    1. Problems, reductions and completeness

Recommendations

An algorithm for selection of migration candidates
MICRO 17: Proceedings of the 17th annual workshop on Microprogramming

The NP-Completeness of the selection problem of vertical migration candidates is shown by reducing it to the NP-complete knapsack problem. Based on approximation algorithms for the latter problem a new algorithm is presented, which takes into account ...
Improving Total Migration Time in Live Virtual Machine Migration
ICCCT '15: Proceedings of the Sixth International Conference on Computer and Communication Technology 2015

Virtualization is the key underlying technology enabling cloud providers to host services for a large number of customers. Live migration is an essential feature of virtualization that allows transfer of virtual machines from one physical server to ...
A Virtual Machine Migration Algorithm Based on Group Selection in Cloud Data Center
Network and Parallel Computing
Abstract
Live migration of virtual machine (VM) is a promising technology that helps physical machines (PMs) adapt to load changes and guarantees Quality of Service (QoS) in cloud data center. Many individual-based VM migration studies ignore the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMICRO Newsletter

ACM SIGMICRO Newsletter Volume 15, Issue 4

MICRO 17: Proceedings of the Seventeenth Annual Microprogramming Workshop

Dec. 1984

302 pages

ISSN:1050-916X

DOI:10.1145/384281

Issue’s Table of Contents

MICRO 17: Proceedings of the 17th annual workshop on Microprogramming
December 1984
325 pages
Chairmen:
M. Carter,
R. A. Mueller

Copyright © 1984 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 1984

Published in SIGMICRO Volume 15, Issue 4

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
163
Total Downloads

Downloads (Last 12 months)35
Downloads (Last 6 weeks)3

Reflects downloads up to 23 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Charlton CLeng PLittle J(1991)Vertical migration of numerical routines in software and microcodeSoftware—Practice & Experience10.1002/spe.438021030521:3(287-297)Online publication date: 1-Mar-1991
https://dl.acm.org/doi/10.1002/spe.4380210305
Shih L(1990)Microprogramming heritage of RISC design[1990] Proceedings of the 23rd Annual Workshop and Symposium@m_MICRO 23: Microprogramming and Microarchitecture10.1109/MICRO.1990.151454(275-280)Online publication date: 1990
https://doi.org/10.1109/MICRO.1990.151454
Winner R(1988)Naming and Binding in a Vertical Migration EnvironmentIEEE Transactions on Software Engineering10.1109/32.613814:5(599-607)Online publication date: 1-May-1988
https://dl.acm.org/doi/10.1109/32.6138
Winner RCarter E(1986)Automated Vertical Migration to Dynamic MicrocodeIEEE Software10.1109/MS.1986.2337483:4(6-16)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1109/MS.1986.233748
Shih LPapachristou CAllan V(1990)Microprogramming heritage of RISC designProceedings of the 23rd annual workshop and symposium on Microprogramming and microarchitecture10.5555/255237.255294(275-280)Online publication date: 30-Nov-1990
https://dl.acm.org/doi/10.5555/255237.255294
Luque ESorribes TRipoll A(1988)Tuning architecture at run-timeACM SIGMICRO Newsletter10.1145/62197.6220019:1-2(12-16)Online publication date: 1-Jun-1988
https://dl.acm.org/doi/10.1145/62197.62200

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents