Rapid re-engineering of embedded real-time systems via cost-benefit analysis with k-level diagonal search

Jungkeun Park, Minsoo Ryu, Seongsoo Hong, Lucia Lo Bello

Research output: Contribution to journalArticle

1 Citation (Scopus)

Abstract

This paper formulates a problem of embedded real-time system re-engineering and presents a systematic solution. Embedded real-time system re-engineering is defined as an understanding and alteration of a legacy system to guarantee newly imposed performance requirements. The performance requirements may include a real-time throughput and an input-to-output latency. The proposed approach is based on a bottleneck analysis and a nonlinear optimization. The inputs to the approach include a system design specified with a process network accompanied by task graphs and task schedules, and a new real-time throughput requirement specified as a system's period constraint. The output is a set of scaling factors that represent the ratios of performance upgrades for processing elements. The solution approach works in two steps. First, it identifies bottleneck processes by estimating process latencies and by analyzing resource sharing among processes. It then derives a set of linear constraints from the new throughput requirement for bottleneck processes. Second, it formulates an integer nonlinear optimization problem and solves it for scaling factors with an objective of minimizing the hardware upgrade cost. Resultant scaling factors are used for cost-effective upgrades of processing elements. To efficiently find feasible solutions, we propose the k-level diagonal search algorithm which runs in a polynomial time with respect to the number of processing elements. Simulation results also confirm this assertion.

Original languageEnglish
Pages (from-to)257-266
Number of pages10
JournalProceedings - Real-Time Systems Symposium
DOIs
StatePublished - 2001 Jan 1

Fingerprint

Cost benefit analysis
Real time systems
Embedded systems
Throughput
Processing
Legacy systems
Costs
Systems analysis
Polynomials
Hardware

Cite this

@article{493d3860f66e49aeb01d67191cf44211,
title = "Rapid re-engineering of embedded real-time systems via cost-benefit analysis with k-level diagonal search",
abstract = "This paper formulates a problem of embedded real-time system re-engineering and presents a systematic solution. Embedded real-time system re-engineering is defined as an understanding and alteration of a legacy system to guarantee newly imposed performance requirements. The performance requirements may include a real-time throughput and an input-to-output latency. The proposed approach is based on a bottleneck analysis and a nonlinear optimization. The inputs to the approach include a system design specified with a process network accompanied by task graphs and task schedules, and a new real-time throughput requirement specified as a system's period constraint. The output is a set of scaling factors that represent the ratios of performance upgrades for processing elements. The solution approach works in two steps. First, it identifies bottleneck processes by estimating process latencies and by analyzing resource sharing among processes. It then derives a set of linear constraints from the new throughput requirement for bottleneck processes. Second, it formulates an integer nonlinear optimization problem and solves it for scaling factors with an objective of minimizing the hardware upgrade cost. Resultant scaling factors are used for cost-effective upgrades of processing elements. To efficiently find feasible solutions, we propose the k-level diagonal search algorithm which runs in a polynomial time with respect to the number of processing elements. Simulation results also confirm this assertion.",
author = "Jungkeun Park and Minsoo Ryu and Seongsoo Hong and {Lo Bello}, Lucia",
year = "2001",
month = "1",
day = "1",
doi = "10.1109/REAL.2001.990620",
language = "English",
pages = "257--266",
journal = "Proceedings - Real-Time Systems Symposium",
issn = "1052-8725",

}

Rapid re-engineering of embedded real-time systems via cost-benefit analysis with k-level diagonal search. / Park, Jungkeun; Ryu, Minsoo; Hong, Seongsoo; Lo Bello, Lucia.

In: Proceedings - Real-Time Systems Symposium, 01.01.2001, p. 257-266.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Rapid re-engineering of embedded real-time systems via cost-benefit analysis with k-level diagonal search

AU - Park, Jungkeun

AU - Ryu, Minsoo

AU - Hong, Seongsoo

AU - Lo Bello, Lucia

PY - 2001/1/1

Y1 - 2001/1/1

N2 - This paper formulates a problem of embedded real-time system re-engineering and presents a systematic solution. Embedded real-time system re-engineering is defined as an understanding and alteration of a legacy system to guarantee newly imposed performance requirements. The performance requirements may include a real-time throughput and an input-to-output latency. The proposed approach is based on a bottleneck analysis and a nonlinear optimization. The inputs to the approach include a system design specified with a process network accompanied by task graphs and task schedules, and a new real-time throughput requirement specified as a system's period constraint. The output is a set of scaling factors that represent the ratios of performance upgrades for processing elements. The solution approach works in two steps. First, it identifies bottleneck processes by estimating process latencies and by analyzing resource sharing among processes. It then derives a set of linear constraints from the new throughput requirement for bottleneck processes. Second, it formulates an integer nonlinear optimization problem and solves it for scaling factors with an objective of minimizing the hardware upgrade cost. Resultant scaling factors are used for cost-effective upgrades of processing elements. To efficiently find feasible solutions, we propose the k-level diagonal search algorithm which runs in a polynomial time with respect to the number of processing elements. Simulation results also confirm this assertion.

AB - This paper formulates a problem of embedded real-time system re-engineering and presents a systematic solution. Embedded real-time system re-engineering is defined as an understanding and alteration of a legacy system to guarantee newly imposed performance requirements. The performance requirements may include a real-time throughput and an input-to-output latency. The proposed approach is based on a bottleneck analysis and a nonlinear optimization. The inputs to the approach include a system design specified with a process network accompanied by task graphs and task schedules, and a new real-time throughput requirement specified as a system's period constraint. The output is a set of scaling factors that represent the ratios of performance upgrades for processing elements. The solution approach works in two steps. First, it identifies bottleneck processes by estimating process latencies and by analyzing resource sharing among processes. It then derives a set of linear constraints from the new throughput requirement for bottleneck processes. Second, it formulates an integer nonlinear optimization problem and solves it for scaling factors with an objective of minimizing the hardware upgrade cost. Resultant scaling factors are used for cost-effective upgrades of processing elements. To efficiently find feasible solutions, we propose the k-level diagonal search algorithm which runs in a polynomial time with respect to the number of processing elements. Simulation results also confirm this assertion.

UR - http://www.scopus.com/inward/record.url?scp=0035684148&partnerID=8YFLogxK

U2 - 10.1109/REAL.2001.990620

DO - 10.1109/REAL.2001.990620

M3 - Article

AN - SCOPUS:0035684148

SP - 257

EP - 266

JO - Proceedings - Real-Time Systems Symposium

JF - Proceedings - Real-Time Systems Symposium

SN - 1052-8725

ER -