Efficient Timing Budget Management for Accuracy Improvement in a Collaborative Object Tracking System

This paper presents the idea of managing the comprising computations of an application performed by an embedded networked system. An efficient algorithm for exploiting the timing slack of building blocks of the application is proposed. The slack of blocks can be utilized by replacing them with slower but cheaper, i.e. better, modules and by assigning the computations to the proper resources. Thus, our approach manages the comprising computations and system resources and can indirectly assist the realtime scheduling of computations on system resources. This is performed without compromising the timing constraints of the application and can lead to significant improvements in power dissipation, computation accuracy or other metrics of the application domain. Our algorithm is well-suited for arbitrary tree computations. Moreover, it delivers solutions that are desirably close to the optimal solution. Experimental results for a number of object tracking applications implemented in an networked system with embedded computation resources, exhibit a significant amount of slack utilization. Soheil Ghiasi received his B.S. from Sharif University of Technology, Tehran, Iran in 1998, and his M.S. and Ph.D. in Computer Science from the University of California, Los Angeles in 2002 and 2004, respectively. Currently, he is an assistant professor in the department of electrical and computer engineering at the University of California, Davis. His research interests include different aspects of Embedded and Reconfigurable system design. Elaheh Bozorgzadeh received the B.S. degree in Electrical Engineering from Sharif University of Technology, Iran in 1998, M.S. degree in Computer Engineering from Northwestern University in 2000, and Ph.D. degree in Computer Science from the University of California, Los Angeles, in 2003. She is currently as assistant professor in the Department of Computer Science at the University of California, Irvine. Her research interest includes VLSI CAD, design automation for embedded systems, and reconfigurable computing. She is a member of ACM and IEEE. Karlene Nguyen received her B.S. and M.S. from University of California, Los Angeles in 2001 and 2003, respectively. She has been working with Prof. Majid Sarrafzadeh for her M.S. degree. Her research interests include embedded hardware and software design. Majid Sarrafzadeh received his B.S., M.S. and Ph.D. in 1982, 1984, and 1987 respectively from the University of Illinois at Urbana-Champaign in Electrical and Computer Engineering. He joined Northwestern University as an Assistant Professor in 1987. In 2000, he joined the Computer Science Department at University of California at Los Angeles (UCLA). His recent research interests lie in the area of Embedded and Reconfigurable Computing, VLSI CAD, and design and analysis of algorithms. Dr. Sarrafzadeh is a Fellow of IEEE for his contribution to “Theory and Practice of VLSI Design.” He received an NSF Engineering Initiation award, two distinguished paper awards in ICCAD, and the best paper award in DAC. He has served on the technical program committee of numerous conferences in the area of VLSI Design and CAD, including ICCAD, DAC, EDAC, ISPD, FPGA, and DesignCon. He has served as committee chairs of a number of these conferences. He is on the executive committee/steering committee of several conferences such as ICCAD, ISPD, and ISQED. He is the program committee chair of ICCAD 2004. Professor Sarrafzadeh has published approximately 250 papers, is a co-editor of the book “Algorithmic Aspects of VLSI Layout” (1994 by World Scientific), and co-author of the book “An Introduction to VLSI Physical Design” (1996 by McGraw Hill). Dr. Sarrafzadeh is an Associate Editor of ACM Transaction on Design Automation (TODAES) and an Associate Editor of IEEE Transactions on Computer-Aided Design (TCAD) and ACM Transactions on design Automation (TODAES). Dr. Sarrafzadeh has collaborated with many industries in the past fifteen years including IBM, Motorola, and many CAD industries. He is the architect of the physical design subsystem of Monterey Design Systems main product. He is a co-founder of Hier Design, Inc.