共查询到10条相似文献,搜索用时 140 毫秒
1.
The execution time of software for hard real-time systems must be predictable. Further, safe and not overly pessimistic bounds
for the worst-case execution time (WCET) must be computable. We conceived a programming strategy called WCET-oriented programming
and a code transformation strategy, the single-path conversion, that aid programmers in producing code that meets these requirements.
These strategies avoid and eliminate input-data dependencies in the code. The paper describes the formal analysis, based on
abstract interpretation, that identifies input-data dependencies in the code and thus forms the basis for the strategies provided
for hard real-time code development.
This work has been supported by the ARTIST2 Network of Excellence on Embedded Systems Design of IST FP6.
Raimund Kirner is an assistant professor in computer science in the Real-Time Systems Group of the Vienna University of Technology. He received
a Master's degree in computer science and a doctoral degree in technical sciences both from the Vienna University of Technology
in Austria in the years 2000 and 2003, respectively. His research interests include worst-case execution time analysis, compiler
support for worst-case execution time analysis, and the verification of real-time systems.
Peter Puschner is a professor in computer science at Vienna University of Technology. His main research focus is on worst-case execution
time (WCET) analysis for real-time programs. Puschner has been working on WCET analysis for more than ten years and has strongly
influenced the state of the art in this field. He has published numerous papers on WCET analysis and software/hardware architectures
supporting temporal predictability. He was a guest editor for the special issue on WCET analysis of the Kluwer International
Journal on Real-Time Systems and chaired the program committee of the IEEE International Symposium on Object-oriented Real-time
distributed Computing in 2003 and the Euromicro Real-Time Systems Conference in 2004. In 2000/2001 Peter Puschner spent one
year as a Marie-Curie research fellow at the University of York, England. 相似文献
2.
This paper discusses aspects of dependability of real-time communication. In particular, we consider timing behaviour under fault conditions for Controller Area Network (CAN) and the extension Time-triggered CAN (TTCAN) based on a time-driven schedule. We discuss the differences between these buses and their behaviour under electromagnetic interference. We present response timing analyses for CAN and TTCAN in the presence of transient network faults using a probabilistic fault model where random faults from electromagnetic interference occur. The CAN analysis provides a probability distribution of worst case response times for message frames. The results indicate that CAN may generally provide a higher probability of delivering messages on time than TTCAN. The CAN analysis result is used to discuss an approach to implementing a bus guardian for event-triggered systems.Ian Broster is a research associate at the University of York, his research includes real-time communication and work on the CAN protocol. Current research focuses on next-generation flexible scheduling for real-time operating systems. His research interests include probabilistic analysis, timing analysis of non-deterministic systems, flexible scheduling, real-time communication, simulation and modelling. He received his M.Eng. degree in 1999 and a Ph.D. in 2003 for his work on flexible real-time communication at the University of York, U.K.Alan Burns has worked for many years on a number of different aspects of real-time systems engineering. He graduated in 1974 in Mathematics from Sheffield University; he then took a D.Phil, in the Computer Science Department at the University of York. After a short period of employment at UKAEA Research Centre, Harwell, he was appointed to a lectureship at Bradford University in 1979. He was subsequently promoted to Senior Lecturer in 1986. In January 1990 he took up a Readership at the University of York in the Computer Science Department. During 1994 he was promoted to a Personal Chair. In 1999 he became Head of the Computer Science Department at York.Guillermo Rodríguez-Navas holds a degree in Telecommunication Engineering by the University of Vigo, Spain. He is currently doing a Ph.D. in Computer Science at the University of the Balearic Islands, Spain. He is also a member of the System, Robotics and Vision (SRV) research group at this university. His research is focused on dependable and real-time distributed embedded systems. In particular, he has addressed various issues related to the Controller Area Network (CAN) field bus, such as fault tolerance, clock synchronization and response time analysis. 相似文献
3.
The problem of scheduling weakly hard real-time tasks is addressed in this paper.The paper first analyzes the characters of μ-pattern and weakly hard real-time constraints,then,presents two scheduling algorithms,Meet Any Algorithm and Meet Row Algorithm,for weakly hard real-time systems.Different from traditional algorithms used to guarantee deadlines,MeetAny Algorithm and Meet Row Algorithm can guarantee both deadlines and constraints.Meet Any Algorithm and Meet Row Algorithm try to find out the probabilities of tasks breaking constraints and increase task‘s priority in advance,but not till the last moment.Simulation results show that these two algorithms are better than other scheduling algorithms dealing with constraints and can largely decrease worst-case computation time of real-time tasks. 相似文献
4.
Sathish Gopalakrishnan Marco Caccamo Chi-Sheng Shih Chang-Gun Lee Lui Sha 《Real-Time Systems》2006,33(1-3):47-75
Timing constraints for radar tasks are usually specified in terms of the minimum and maximum temporal distance between successive
radar dwells. We utilize the idea of feasible intervals for dealing with the temporal distance constraints. In order to increase
the freedom that the scheduler can offer a high-level resource manager, we introduce a technique for nesting and interleaving
dwells online while accounting for the energy constraint that radar systems need to satisfy. Further, in radar systems, the
task set changes frequently and we advocate the use of finite horizon scheduling in order to avoid the pessimism inherent
in schedulers that assume a task will execute forever. The combination of feasible intervals and online dwell packing allows
modular schedule updates whereby portions of a schedule can be altered without affecting the entire schedule, hence reducing
the complexity of the scheduler. Through extensive simulations we validate our claims of providing greater scheduling flexibility
without compromising on performance when compared with earlier work based on templates constructed offline. We also evaluate
the impact of two parameters in our scheduling approach: the template length (or the extent of dwell nesting and interleaving)
and the length of the finite horizon.
Sathish Gopalakrishnan is a visting scholar in the Department of Computer Science, University of Illinois at Urbana-Champaign, where he defended
his Ph.D. thesis in December 2005. He received an M.S. in Applied Mathematics from the University of Illinois in 2004 and
a B.E. in Computer Science and Engineering from the University of Madras in 1999. Sathish’s research interests concern real-time
and embedded systems, and the design of large-scale reliable systems. He received the best student paper award for his work
on radar dwell scheduling at the Real-Time Systems Symposium 2004.
Marco Caccamo graduated in computer engineering from the University of Pisa in 1997 and received the Ph.D. degree in computer engineering
from the Scuola Superiore S. Anna in 2002. He is an Assistant Professor of the Department of Computer Science at the University
of Illinois. His research interests include real-time operating systems, real-time scheduling and resource management, wireless
sensor networks, and quality of service control in next generation digital infrastructures. He is recipient of the NSF CAREER
Award (2003). He is a member of ACM and IEEE.
Chi-Sheng Shih is currently an assistant professor at the Graduate Institute of Networking and Multimedia and Department of Computer Science
and Information Engineering at National Taiwan University since February 2004. He received the B.S. in Engineering Science
and M.S. in Computer Science from National Cheng Kung University in 1993 and 1995, respectively. In 2003, he received his
Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign. His main research interests are embedded systems,
hardware/software codesign, real-time systems, and database systems. Specifically, his main research interests focus on real-time
operating systems, real-time scheduling theory, embedded software, and software/hardware co-design for system-on-a-chip.
Chang-Gun Lee received the B.S., M.S. and Ph.D. degrees in computer engineering from Seoul National University, Korea, in 1991, 1993 and
1998, respectively. He is currently an Assistant Professor in the Department of Electrical Engineering, Ohio State University,
Columbus. Previously, he was a Research Scientist in the Department of Computer Science, University of Illinois at Urbana-Champaign
from March 2000 to July 2002 and a Research Engineer in the Advanced Telecomm. Research Lab., LG Information & Communications,
Ltd. from March 1998 to February 2000. His current research interests include real-time systems, complex embedded systems,
QoS management, and wireless ad-hoc networks. Chang-Gun Lee is a member of the IEEE Computer Society.
Lui Sha graduated with the Ph.D. degree from Carnegie-Mellon University in 1985. He was a Member and then a Senior Member of Technical
Staff at Software Engineering Institute (SEI) from 1986 to 1998. Since Fall 1998, he has been a Professor of Computer Science
at the University of Illinois at Urbana Champaign, and a Visiting Scientist of the SEI. He was the Chair of IEEE Real Time
Systems Technical Committee from 1999 to 2000, and has served on its Executive Committee since 2001. He was a member of National
Academy of Science’s study group on Software Dependability and Certification from 2004 to 2005, and is an IEEE Distinguished
Visitor (2005 to 2007). Lui Sha is a Fellow of the IEEE and the ACM. 相似文献
5.
6.
This paper addresses the problem of resource allocation for distributed real-time periodic tasks, operating in environments
that undergo unpredictable changes and that defy the specification of meaningful worst-case execution times. These tasks are
supplied by input data originating from various environmental workload sources. Rather than using worst-case execution times
(WCETs) to describe the CPU usage of the tasks, we assume here that execution profiles are given to describe the running time
of the tasks in terms of the size of the input data of each workload source. The objective of resource allocation is to produce
an initial allocation that is robust against fluctuations in the environmental parameters. We try to maximize the input size
(workload) that can be handled by the system, and hence to delay possible (costly) reallocations as long as possible. We present
an approximation algorithm based on first-fit and binary search that we call FFBS. As we show here, the first-fit algorithm
produces solutions that are often close to optimal. In particular, we show analytically that FFBS is guaranteed to produce
a solution that is at least 41% of optimal, asymptotically, under certain reasonable restrictions on the running times of
tasks in the system. Moreover, we show that if at most 12% of the system utilization is consumed by input independent tasks
(e.g., constant time tasks), then FFBS is guaranteed to produce a solution that is at least 33% of optimal, asymptotically.
Moreover, we present simulations to compare FFBS approximation algorithm with a set of standard (local search) heuristics
such as hill-climbing, simulated annealing, and random search. The results suggest that FFBS, in combination with other local
improvement strategies, may be a reasonable approach for resource allocation in dynamic real-time systems.
David Juedes is a tenured associate professor and assistant chair for computer science in the School of Electrical Engineering and Computer
Science at Ohio University. Dr. Juedes received his Ph.D. in Computer Science from Iowa State University in 1994, and his
main research interests are algorithm design and analysis, the theory of computation, algorithms for real-time systems, and
bioinformatics. Dr. Juedes has published numerous conference and journal papers and has acted as a referee for IEEE Transactions
on Computers, Algorithmica, SIAM Journal on Computing, Theoretical Computer Science, Information and Computation, Information
Processing Letters, and other conferences and journals.
Dazhang Gu is a software architect and researcher at Pegasus Technologies (NeuCo), Inc. He received his Ph.D. in Electrical Engineering
and Computer Science from Ohio University in 2005. His main research interests are real-time systems, distributed systems,
and resource optimization. He has published conference and journal papers on these subjects and has refereed for the Journal
of Real-Time Systems, IEEE Transactions on Computers, and IEEE Transactions on Parallel and Distributed Systems among others.
He also served as a session chair and publications chair for several conferences.
Frank Drews is an Assistant Professor of Electical Engineering and Computer Science at Ohio Unversity. Dr. Drews received his Ph.D. in
Computer Science from the Clausthal Unversity of Technolgy in Germany in 2002. His main research interests are resource management
for operating systems and real-time systems, and bioinformatics. Dr. Drews has numerous publications in conferences and journals
and has served as a reviewer for IEEE Transactions on Computers, the Journal of Systems and Software, and other conferences
and Journals. He was Publication Chair for the OCCBIO’06 conference, Guest Editor of a Special Issue of the Journal of Systems
and Software on “Dynamic Resource Management for Distributed Real-Time Systems”, organizer of special tracks at the IEEE IPDPS
WPDRTS workshops in 2005 and 2006.
Klaus Ecker received his Ph.D. in Theoretical Physics from the University of Graz, Austria, and his Dr. habil. in Computer Science from
the University of Bonn. Since 1978 he is professor in the Department of Computer Science at the Clausthal University of Technology,
Germany, and since 2005 he is visiting professor at the Ohio University. His research interests are parallel processing and
theory of scheduling, especially in real time systems, and bioinformatics. Prof. Ecker published widely in the above mentioned
areas in well reputed journals and proceedings of international conferences as well. He is also the author of two monographs
on scheduling theory. Since 1981 he is organizing annually international workshops on parallel processing. He is associate
editor of Real Time Systems, and member of the German Gesellschaft fuer Informatik (GI) and of the Association for Computing
Machinery (ACM).
Lonnie R. Welch received a Ph.D. in Computer and Information Science from the Ohio State University. Currently, he is the Stuckey Professor
of Electrical Engineering and Computer Science at Ohio University. Dr. Welch performs research in the areas of real-time systems,
distributed computing and bioinformatics. His research has been sponsored by the Defense Advanced Research Projects Agency,
the Navy, NASA, the National Science Foundation and the Army. Dr. Welch has twenty years of research experience in the area
of high performance computing. In his graduate work at Ohio State University, he developed a high performance 3-D graphics
rendering algorithm, and he invented a parallel virtual machine for object-oriented software. For the past 15 years his research
has focused on middleware and optimization algorithms for high performance computing. His research has produced three successive
generations of adaptive resource management (RM) middleware for high performance real-time systems. The project has resulted
in two patents and more than 150 publications. Professor Welch also collaborates on diabetes research with faculty at Edison
Biotechnology Institute and on genomics research with faculty in the Department of Environmental and Plant Biology at Ohio
University. Dr. Welch is a member of the editorial boards of IEEE Transactions on Computers, The Journal of Scalable Computing:
Practice and Experience, and The International Journal of Computers and Applications. He is also the founder of the International
Workshop on Parallel and Distributed Real-time Systems and of the Ohio Collaborative Conference on Bioinformatics.
Silke Schomann graduated in 2003 with a M.Sc. in Computer Science from Clausthal University Of Technology, where she has been working as
a scientific assistant since then. She is currently working on her Ph.D. thesis in computer science at the same university. 相似文献
7.
Pre-Scheduling 总被引:1,自引:0,他引:1
Static scheduling has been well accepted for its predictability and online simplicity. Traditional static schedule generation techniques are usually based on the assumption of constant rate of resource supply known at design time. Under resource composition schemes, however, this assumption may not be valid for a workload to be statically scheduled. A pre-schedule is a static schedule without assuming constant and completely predictable rate of resource supply. In this paper, concepts of supply function and supply contract are introduced to define the actual online resource supply rate and the constraints to this rate known off-line. Based on these concepts, this paper defines the pre-scheduling problem, and presents a sound, complete, and PTIME pre-scheduler.This research is supported partially by grants from the Office of Naval Research under ONR contract N00014-03-1-0705 and the National Science Foundation under NSF grant CCR0207853.Weirong Wang received B.E. in computer engineering from Beijing University of Technology, M.A. and Ph.D. in computer science from the University of Texas at Austin. He is currently an automation engineer in Intel. His research interests include real-time and embedded systems, software engineering and algorithms.Aloysius K. Mok Aloysius K. Mok is Quincy Lee Centennial Professor in Computer Science at the University of Texas at Austin. He received the S.B. in electrical engineering, the S.M. in electrical engineering and computer science and the Ph.D. degrees in computer science, all from the Massachusetts Institute of Technology. Since 1983, Dr. Mok been on the faculty of the Department of Computer Sciences at the University of Texas at Austin. Professor Mok has done extensive research on computer software systems and is internationally known for his work in real-time systems. He is a past Chairman of the Techni- cal Committee on Real-Time Systems of the Institute of Electrical and Electronics Engineers, and has served on numerous national and international research and advisory panels. His current interests include real-time and embed- ded systems, robust and secure network-centric computing and real-time knowledge-based systems. Dr. Mok received in 2002 the IEEE TC on Real-Time Systems Award for his outstanding technical contributions and leadership achievements in real-time systems.Gerhard Fohler is Professor and leader of the predictably flexible real-time systems group at SDL. He received his Ph.D. from Vienna University of Technology in 1994 for research towards flexibility for offline scheduling in the MARS system. He then worked at the University of Massachusetts at Amherst as postdoctoral researcher within the SPRING project. During 1996–97, he was a researcher at Humboldt University Berlin, investigating issues of adaptive reliability and real-time. Gerhard Fohler is currently chairman of the Technical Committee on Real-Time Systems of EUROMICRO. 相似文献
8.
A Technique for Adaptive Scheduling of Soft Real-Time Tasks 总被引:1,自引:1,他引:0
A number of multimedia and process control applications can take advantage from the ability to adapt soft real-time load to
available computational capacity. This capability is required, for example, to react to changed operating conditions as well
as to ensure graceful degradation of an application under transient overloads. In this paper, we illustrate a novel adaptive
scheduling technique based on rate modulation of a set of periodic tasks in a range of admissible rates. By casting constraints
on rate ranges in a linear programming formulation, several adaptation policies can be considered, along with additional constraints
reflecting various application requirements. The paper investigates the effectiveness of rate modulation strategies both on
simulated task sets and on real experiments.
Partial support for this research has been provided by MURST, Italy (PRIN project ISIDE on “Dependable reactive computing
systems for industrial applications” and special project “RoboCare” funded by L. 449/97), and by ASI, Agenzia Spaziale Italiana
(contract I/R/134/00).
Giuseppe Beccari received the Laurea degree in Electronic Engineering in 1993, and the Ph.D. in Information Technology in 1999, both from
the University of Parma, Italy. In 1995 he was visiting scholar at the Technical University of Delft, Holland, and at the
Laboratoire de Robotique de Paris, France. In 1999 he was employed by CSELT (Centro Studi E Laboratori Telecomunicazioni,
currently TILAB, the Telecom Italia Group research center). In 2002 he moved to a spin off company involved in the EUROSAM/FSAF
(Future Surface-to-Air Family self defense missile system) project. While his current professional duties focus more on software
development and team coordination, dr. Beccari still enjoys investigating real-time scheduling issues and technology.
Stefano Caselli received a Laurea degree in Electronic Engineering in 1982 and the Ph.D. degree in Computer and Electronic Engineering in
1987, both from the University of Bologna, Italy. In 1989-90 he has been visiting scholar at the University of Florida. From
1990 to 1999 he has held research fellow and associate professor positions at the University of Parma, Italy. He is now professor
of Computer Engineering at the University of Parma, where he is also director of the Laboratory of Robotics and Intelligent
Machines (RIMLab). His current research interests include development of autonomous and remotely operated robot systems, service
robotics, and real-time systems.
Francesco Zanichelli received a Laurea degree in Electronic Engineering in 1987 from the University of Bologna, Italy and the Ph.D. degree in
Information Technologies in 1994 from the University of Parma, Italy. Since 1996 he has been an Assistant Professor with the
Department of Information Engineering of the University of Parma where he is currently teaching Operating Systems, Information
Systems and Multimedia Systems courses. His current research interests include distributed multimedia architectures and protocols,
real-time systems, security and Quality of Service technologies for wireless networks, as well as service-oriented Grid middleware. 相似文献
9.
Wankang Zhao William Kreahling David Whalley Christopher Healy Frank Mueller 《Real-Time Systems》2006,34(2):129-152
It is advantageous to perform compiler optimizations that attempt to lower the worst-case execution time (WCET) of an embedded application since tasks with lower WCETs are easier to schedule and more likely to meet their deadlines.
Compiler writers in recent years have used profile information to detect the frequently executed paths in a program and there
has been considerable effort to develop compiler optimizations to improve these paths in order to reduce the average-case execution time (ACET). In this paper, we describe an approach to reduce the WCET by adapting and applying optimizations designed for frequent
paths to the worst-case (WC) paths in an application. Instead of profiling to find the frequent paths, our WCET path optimization uses feedback from
a timing analyzer to detect the WC paths in a function. Since these path-based optimizations may increase code size, the subsequent
effects on the WCET due to these optimizations are measured to ensure that the worst-case path optimizations actually improve
the WCET before committing to a code size increase. We evaluate these WC path optimizations and present results showing the
decrease in WCET versus the increase in code size.
A preliminary version of this paper entitled “Improving WCET by optimizing worst-case paths” appeared in the 2005 Real-Time and Embedded Technology and Applications Symposium.
Wankang Zhao received his PhD in Computer Science from Florida State University in 2005. He was an associate professor in Nanjin University
of Post and Telecommunications. He is currently working for Datamaxx Corporation.
William Kreahling received his PhD in Computer Science from Florida State University in 2005. He is currently an assistant professor in the
Math and Computer Science department at Western Carolina University. His research interests include compilers, computer architecture
and parallel computing.
David Whalley received his PhD in CS from the University of Virginia in 1990. He is currently the E.P. Miles professor and chair of the
Computer Science department at Florida State University. His research interests include low-level compiler optimizations,
tools for supporting the development and maintenance of compilers, program performance evaluation tools, predicting execution
time, computer architecture, and embedded systems. Some of the techniques that he developed for new compiler optimizations
and diagnostic tools are currently being applied in industrial and academic compilers. His research is currently supported
by the National Science Foundation. More information about his background and research can be found on his home page, http://www.cs.fsu.edu/∼whalley.
Dr. Whalley is a member of the IEEE Computer Society and the Association for Computing Machinery.
Chris Healy earned a PhD in computer science from Florida State University in 1999, and is currently an associate professor of computer
science at Furman University. His research interests include static and parametric timing analysis, real-time and embedded
systems, compilers and computer architecture. He is committed to research experiences for undergraduate students, and his
work has been supported by funding from the National Science Foundation. He is a member of ACM and the IEEE Computer Society.
Frank Mueller is an Associate Professor in Computer Science and a member of the Centers for Embedded Systems Research (CESR) and High Performance
Simulations (CHiPS) at North Carolina State University. Previously, he held positions at Lawrence Livermore National Laboratory
and Humboldt University Berlin, Germany. He received his Ph.D. from Florida State University in 1994. He has published papers
in the areas of embedded and real-time systems, compilers and parallel and distributed systems. He is a founding member of
the ACM SIGBED board and the steering committee chair of the ACM SIGPLAN LCTES conference. He is a member of the ACM, ACM
SIGPLAN, ACM SIGBED and the IEEE Computer Society. He is a recipient of an NSF Career Award. 相似文献
10.
Verifying distributed real-time properties of embedded systems via graph transformations and model checking 总被引:1,自引:0,他引:1
Component middleware provides dependable and efficient platforms that support key functional, and quality of service (QoS)
needs of distributed real-time embedded (DRE) systems. Component middleware, however, also introduces challenges for DRE system
developers, such as evaluating the predictability of DRE system behavior, and choosing the right design alternatives before
committing to a specific platform or platform configuration. Model-based technologies help address these issues by enabling
design-time analysis, and providing the means to automate the development, deployment, configuration, and integration of component-based
DRE systems. To this end, this paper applies model checking techniques to DRE design models using model transformations to
verify key QoS properties of component-based DRE systems developed using Real-time CORBA. We introduce a formal semantic domain
for a general class of DRE systems that enables the verification of distributed non-preemptive real-time scheduling. Our results
show that model-based techniques enable design-time analysis of timed properties and can be applied to effectively predict,
simulate, and verify the event-driven behavior of component-based DRE systems.
This research was supported by the NSF Grants CCR-0225610 and ACI-0204028
Gabor Madl is a Ph.D. student and a graduate student researcher at the Center for Embedded Computer Systems at the University of California,
Irvine. His advisor is Nikil Dutt. His research interests include the formal verification, optimization, component-based composition,
and QoS management of distributed real-time embedded systems. He received his M.S. in computer science from Vanderbilt University
and in computer engineering from the Budapest University of Technology and Economics.
Dr. Sherif Abdelwahed received his Ph.D. degree in Electrical and Computer Engineering from the University of Toronto, Canada, in 2001. During
2000–2001, he was a research scientist with the system diagnosis group at the Rockwell Scientific Company. Since 2001 he has
been with the Department of Electrical Engineering and Computer Science at Vanderbilt University as a Research Assistant Professor.
His research interests include verification and control of distributed real-time systems, and model-based diagnosis of discrete-event
and hybrid systems.
Dr. Douglas C. Schmidt is a Professor of Computer Science, Associate Chair of the Computer Science and Engineering program, and a Senior Researcher
in the Institute for Software Integrated Systems (ISIS) all at Vanderbilt University. He has published over 300 technical
papers and 6 books that cover a range of research topics, including patterns, optimization techniques, and empirical analyses
of software frameworks and domain-specific modeling environments that facilitate the development of distributed real-time
and embedded (DRE) middleware and applications. Dr. Schmidt has served as a Deputy Office Director and a Program Manager at
DARPA, where he lead the national R&D effort on middleware for DRE systems. In addition to his academic research and government
service, Dr. Schmidt has over fifteen years of experience leading the development of ACE, TAO, CIAO, and CoSMIC, which are
widely used, open-source DRE middleware frameworks and model-driven tools that contain a rich set of components and domain-specific
languages that implement patterns and product-line architectures for high-performance DRE systems. 相似文献