Search

With the increase in process variations and diversity in workloads, it is imperative to holistically explore optimization techniques for power and temperature from the circuit layer right up to the compiler/operating system (OS) layer. This article proposes one such holistic technique, called proactive workload aware temperature management framework for low-power chip multi-processors (ProWATCh). At the compiler level ProWATCh includes two techniques: (1) a novel compiler design for estimating the architectural parameters of a task at compile time, and (2) a model-based technique for dynamic estimation of architectural parameters at runtime. At the OS level ProWATCh integrates two techniques: (1) a workload- and temperature-aware process manager for dynamic distribution of tasks to different cores, and (2) a model predictive control-based task scheduler for generating the efficient sequence of task execution. At the circuit level ProWATCh implements either of two techniques: (1) a workload-aware voltage manager for dynamic supply and body bias voltage assignment for a given frequency in processors that support adaptive body bias (ABB), or (2) a workload-aware frequency governor for efficient assignment of upper and lower frequency bounds for frequency scaling in processors that do not support an ABB. Employing ProWATCh (with voltage manager) on an ABB-compatible 3D OpenSPARC architecture using MiBench benchmarks resulted in an average 18% (19�C) reduction in peak temperature. Evaluating ProWATCh on an existing quad-core Intel Corei7 processor with frequency governor alone (as the processor does not support an ABB interface) resulted in 10% (8�C) reduction in peak temperature when compared to what was obtained using the native Linux 3.0 completely fair scheduler (CFS). To study the effectiveness of the proposed framework across benchmark suites, ProWATCh was evaluated on a quad-core Intel Corei7 processor using CPU SPEC 2006 benchmarks which resulted in 7�C reduction in peak temperature as compared to the native Linux 3.0 CFS. � 2015 ACM.

Networks-on-Chips (NoCs) are experiencing escalating susceptibility to wear-out and reduced reliability, with the risk of becoming the key point of failure in an entire multicore chip. In this paper we propose Hermes, a highly-robust, distributed fault-tolerant routing algorithm, whose performance degrades gracefully with increasing faulty NoC link counts. Hermes is a deadlock-free hybrid routing algorithm, utilizing load-balanced routing on fault-free paths, while providing pre-reconfigured escape routes in the vicinity of faults. An initial experimental evaluation shows that Hermes improves network throughput by up to 2.2× when compared against the existing state-of-the-art.

Correct and efficient implementation of general real-time applications remains by far an open problem. A key issue is meeting timing constraints whose satisfaction depends on features of the execution platform, in particular its speed. Existing rigorous implementation techniques are applicable to specific classes of systems e.g. with periodic tasks, time deterministic systems.We present a general model-based implementation method for real-time systems based on the use of two models. An abstract model representing the behavior of real-time software as a timed automaton. The latter describes user-defined platform-independent timing constraints. Its transitions are timeless and correspond to the execution of statements of the real-time software.A physical model representing the behavior of the real-time software running on a given platform. It is obtained by assigning execution times to the transitions of the abstract model.A necessary condition for implementability is time-safety, that is, any (timed) execution sequence of the physical model is also an execution sequence of the abstract model. Time-safety simply means that the platform is fast enough to meet the timing requirements. As execution times of actions are not known exactly, time-safety is checked for worst-case execution times of actions by making an assumption of time-robustness: time-safety is preserved when speed of the execution platform increases.We show that as a rule, physical models are not time-robust and show that time-determinism is a sufficient condition for time-robustness.For given real-time software and execution platform corresponding to a time-robust model, we define an Execution Engine that coordinates the execution of the application software so as to meet its timing constraints. Furthermore, in case of non-robustness, the Execution Engine can detect violations of time-safety and stop execution.We have implemented the Execution Engine for BIP programs with real-time constraints. We have validated the implementation method for an adaptive MPEG video encoder. Experimental results reveal the existence of timing anomalies seriously degrading performance for increasing platform execution speed.

Paxos is a well known algorithm for achieving consensus in distributed environments with uncertain processing and communication timing. Implementations of its variants have been successfully used in the industry (eg., Chubby by Google, Autopilot cluster management in Bing by Microsoft, and many others). This paper addresses the challenge of the manual coding of complex distributed algorithms, such as Paxos, where this is an error prone process. Our approach in ensuring correct implementation is to use a verified automated translator to compile a source specification that has been proven to be itself correct. We use specification of the Paxos algorithm in the General Timed Automata (GTA) model, an extension of I/O Automata, as input to an augmented compiler for the Input/Output Automata notation (a.k.a., the IOA compiler) in order to generate executable Java code. The resulting code is interfaced with MPI for communication needs. We have extended the IOA compiler to support a version of the GTA model, which uses time-passage actions such as ν(t), to model the passage of time by t time units. A time-based version of Paxos is used to demonstrate the capabilities of our extension. In this paper we describe the process to be followed in order to compile time-based Paxos, or similar algorithms. The utility of our approach is supported by an experimental evaluation of our Paxos implementation on a collection of workstations. To the best of our knowledge, our case study constitutes the first example of a time-dependent distributed algorithm that has been specified, verified and implemented in an automated way, using a common formal methodology. © 2010 Springer-Verlag. 6490 LNCS 235 252 Conference code: 83362

A multistage algorithm is proposed that will solve the scheduling problem in a flexible manufacturing system by considering the interrelated subproblems of processing time control, tool allocation and machining conditions optimization. The main objective of the proposed algorithm is to minimize total production cost consisting of tooling, operational and tardiness costs. The proposed integrated approach recognizes an important trade-off in automated manufacturing systems that has been largely unrecognized, and which is believed can be effectively exploited to improve production efficiency and lead to substantial cost reductions.

This innovative approach eliminates the traditional instruction set interface and instead exposes the details of a simple replicated architecture directly to the compiler. This allows the compiler to customize the hardware to each application.

Date of Conference: 12-14 April 1994 Conference Name: 7th Mediterranean Electrotechnical Conference, MELECON 1994 Vector processors have promised an enormous increase in computing speed for computationally intensive and time-critical power system problems which require the repeated solution of sparse linear equations. Due to short vectors processed in these applications, standard sparsity-based algorithms need to be restructured for efficient vectorization. This paper presents a novel data storage scheme and an efficient vectorization algorithm that exploits the intrinsic architectural features of vector computers such as sectioning and chaining. As the benchmark, the solution phase of the Fast Decoupled Load Flow algorithm is used in simulations. The relative performances of the proposed and existing vectorization schemes are evaluated, both theoretically and experimentally, on IBM 3090/VF.

In this paper we present an optimal linear time algorithm for recognition and parsing of context-free languages on n ? n mesh connected computers with multiple broadcasting, for an input string of length n. Our algorithm is based on the well-known Cocke-Younger-Kasami (CYK) algorithm for the recognition and parsing of context-free languages, and is faster than two recent algorithms available in the literature. The parallel recognition of context-free languages is of particular importance since parallel compilation is an increasingly important application because of the availability of parallel hardware and the long running times of optimizing and parallelizing compilers. Our algorithm is a contribution towards this end. ? 1994.

Code optimisation algorithms using bi-directional data flow dependencies have become increasingly important in recent years. The use of these algorithms faces two difficulties in practice: (a) Low profitabilities, and (b) high solution costs. This paper develops a new approach to the use of bi-directional dependencies using the concept of edge placement. This is shown to yield higher profitabilities of optimisation. An efficient solution method for such algorithms is also developed. The complexity of this method is shown to be bounded by O(e) operations, where e is the number of edges in the program flow graph. Ths is comparable to the complexity of uni-directional flow algorithms commonly used in optimisation., © ACM