Integrated Modular Avionics (IMA) partition scheduling with conflict-free I/O for multicore avionics systems

Jung Eun Kim, Man Ki Yoon, Richard Bradford, Lui Sha

Research output: Contribution to journalConference article

Abstract

The trend in the semiconductor industry toward multicore processors poses a significant challenge to many suppliers of safety-critical real-time embedded software. Having certified their systems for use on single-core processors, these companies may be forced to migrate their installed base of software onto multicore processors as single-core processors become harder to obtain. These companies naturally want to minimize the potentially high costs of recertifying their software for multicore processors. In support of this goal, we propose an approach to solving a fundamental problem in migrating legacy software applications to multicore systems, namely that of preventing conflicts among I/O transactions from applications residing on different cores. We formalize the problem as a partition scheduling problem that serializes I/O partitions. Although this problem is strongly NP-complete, we formulate it as a Constraint Programming (CP) problem. Since the CP approach scales poorly, we propose a heuristic algorithm that outperforms the CP approach in scalability.

Original languageEnglish (US)
Article number6899233
Pages (from-to)321-331
Number of pages11
JournalProceedings - International Computer Software and Applications Conference
DOIs
StatePublished - Sep 15 2014
Event38th Annual IEEE Computer Software and Applications Conference, COMPSAC 2014 - Vasteras, Sweden
Duration: Jul 21 2014Jul 25 2014

Fingerprint

Avionics
Scheduling
Industry
Embedded software
Heuristic algorithms
Application programs
Scalability
Semiconductor materials
Costs

Keywords

  • Conflict-free I/O
  • Integrated Modular Avionics (IMA)
  • Multicore Avionics Systems

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Cite this

Integrated Modular Avionics (IMA) partition scheduling with conflict-free I/O for multicore avionics systems. / Kim, Jung Eun; Yoon, Man Ki; Bradford, Richard; Sha, Lui.

In: Proceedings - International Computer Software and Applications Conference, 15.09.2014, p. 321-331.

Research output: Contribution to journalConference article

@article{9b10f9110d254359b894c069ecf1729b,
title = "Integrated Modular Avionics (IMA) partition scheduling with conflict-free I/O for multicore avionics systems",
abstract = "The trend in the semiconductor industry toward multicore processors poses a significant challenge to many suppliers of safety-critical real-time embedded software. Having certified their systems for use on single-core processors, these companies may be forced to migrate their installed base of software onto multicore processors as single-core processors become harder to obtain. These companies naturally want to minimize the potentially high costs of recertifying their software for multicore processors. In support of this goal, we propose an approach to solving a fundamental problem in migrating legacy software applications to multicore systems, namely that of preventing conflicts among I/O transactions from applications residing on different cores. We formalize the problem as a partition scheduling problem that serializes I/O partitions. Although this problem is strongly NP-complete, we formulate it as a Constraint Programming (CP) problem. Since the CP approach scales poorly, we propose a heuristic algorithm that outperforms the CP approach in scalability.",
keywords = "Conflict-free I/O, Integrated Modular Avionics (IMA), Multicore Avionics Systems",
author = "Kim, {Jung Eun} and Yoon, {Man Ki} and Richard Bradford and Lui Sha",
year = "2014",
month = "9",
day = "15",
doi = "10.1109/COMPSAC.2014.54",
language = "English (US)",
pages = "321--331",
journal = "Proceedings - IEEE Computer Society's International Computer Software and Applications Conference",
issn = "0730-6512",
publisher = "Institute of Electrical and Electronics Engineers Inc.",

}

TY - JOUR

T1 - Integrated Modular Avionics (IMA) partition scheduling with conflict-free I/O for multicore avionics systems

AU - Kim, Jung Eun

AU - Yoon, Man Ki

AU - Bradford, Richard

AU - Sha, Lui

PY - 2014/9/15

Y1 - 2014/9/15

N2 - The trend in the semiconductor industry toward multicore processors poses a significant challenge to many suppliers of safety-critical real-time embedded software. Having certified their systems for use on single-core processors, these companies may be forced to migrate their installed base of software onto multicore processors as single-core processors become harder to obtain. These companies naturally want to minimize the potentially high costs of recertifying their software for multicore processors. In support of this goal, we propose an approach to solving a fundamental problem in migrating legacy software applications to multicore systems, namely that of preventing conflicts among I/O transactions from applications residing on different cores. We formalize the problem as a partition scheduling problem that serializes I/O partitions. Although this problem is strongly NP-complete, we formulate it as a Constraint Programming (CP) problem. Since the CP approach scales poorly, we propose a heuristic algorithm that outperforms the CP approach in scalability.

AB - The trend in the semiconductor industry toward multicore processors poses a significant challenge to many suppliers of safety-critical real-time embedded software. Having certified their systems for use on single-core processors, these companies may be forced to migrate their installed base of software onto multicore processors as single-core processors become harder to obtain. These companies naturally want to minimize the potentially high costs of recertifying their software for multicore processors. In support of this goal, we propose an approach to solving a fundamental problem in migrating legacy software applications to multicore systems, namely that of preventing conflicts among I/O transactions from applications residing on different cores. We formalize the problem as a partition scheduling problem that serializes I/O partitions. Although this problem is strongly NP-complete, we formulate it as a Constraint Programming (CP) problem. Since the CP approach scales poorly, we propose a heuristic algorithm that outperforms the CP approach in scalability.

KW - Conflict-free I/O

KW - Integrated Modular Avionics (IMA)

KW - Multicore Avionics Systems

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

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

U2 - 10.1109/COMPSAC.2014.54

DO - 10.1109/COMPSAC.2014.54

M3 - Conference article

AN - SCOPUS:84928595574

SP - 321

EP - 331

JO - Proceedings - IEEE Computer Society's International Computer Software and Applications Conference

JF - Proceedings - IEEE Computer Society's International Computer Software and Applications Conference

SN - 0730-6512

M1 - 6899233

ER -