Financial transactions are specified in decimal arithmetic. Until the introduction of IEEE 754-2008, specialized software/hardware routines were used to perform these transactions but it incurred a penalty on performance. In this paper, we show that if binary arithmetic is used to emulate decimal operations, then arbitrary error sequences can be generated by carefully chosen sequences of transactions which can lead to monotonically increasing/decreasing capitalization errors. In addition, we describe methods for correctly performing basic decimal operations, such as addition, subtraction, multiplication, and division, on binary machines, which are not conformant with IEEE 754-2008 decimal floating point standard (ISO/IEC/IEEE 60559:2011), at high speed.

Multimedia applications (also called multimedia systems) operate on datastreams, which are periodic sequences of data elements, called datasets. A large class of multimedia applications is described by the macro-dataflow graph model, with nodes representing parallelizable tasks, and arcs representing communication. This paper examines how such multimedia applications can be compiled to run efficiently on parallel machines, by optimizing both throughput (T) and latency (L), using two techniques, based on task speedup functions. The first step chooses an appropriate pipeline structure for the system (task clustering). The second step exploits the dataset parallelism intrinsic in the periodic datastream, and runs multiple datasets in parallel (task/cluster multiplicity) for each clustering. The key find-of this research areA The best task clustering depends on system throughput. In general skewed parallelism profiles are desirable i.e. tasks with good speedup and tasks with poor speedup are in separate clusters. Indeed the maximal throughput and minimal latency can be simultaneously attained in the limiting case of a maximally skewed distribution. This result can be viewed as a generalization of Amdahl's law for real-time applications.B Optimal dataset multiplicity for a specific clustering can be determined by extending retiming theory [1] to include parallel resource allocation. In this process, counter-intuitive relaxation regions often appear, wherein by increasing dataset multiplicity, throughput is increased and latency simultaneously reduced (a free lunch).The techniques have been used for compiling real-time image-processing problems on an NCUBE-2 multiprocessor, and show substantial performance gains.

The paper considerably extends the multiprocessor scheduling techniques of G.N.S. Prasanna and B.R. Musicus (1995; 1991) and applies it to matrix arithmetic compilation. Using optimal control theory in the special case where the speedup function of each task is p/sup /spl alpha// (where p is the amount of processing power applied to the task), closed form solution for task graphs formed from parallel and series connections was derived by G.N.S. Prasanna and B.R. Musicus (1995; 1991). The paper extends these results for arbitrary DAGS. The optimality conditions impose nonlinear constraints on the flow of processing power from predecessors to successors, and on the finishing times of siblings. The paper presents a fast algorithm for determining and solving these nonlinear equations. The algorithm utilizes the structure of the finishing time equations to efficiently run a conjugate gradient minimization, leading to the optimal solution. The algorithm has been tested on a variety of DAGs commonly encountered in matrix arithmetic. The results show that if the p/sup /spl alpha// speedup assumption holds, the schedules produced are superior to heuristic approaches. The algorithm has been applied to compiling matrix arithmetic (K.P. Belkhale and P. Banerjee, 1993), for the MIT Alewife machine, a distributed shared memory multiprocessor. While matrix arithmetic tasks do not exactly satisfy the p/sup /spl alpha// speedup assumptions, the algorithm can be applied as a good heuristic. The results show that the schedules produced by our algorithm are faster than alternative heuristic techniques.

In the 3rd Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 216-228 (JuIy 1991), we presented several new results in the theory of homogeneous multiprocessor scheduling. A directed acyclic graph (DAG) of tasks was to be scheduled. Tasks were assumed to be parallelizable-as more processors are applied to a task, the time taken to compute it decreases, yielding some speedup. Because of communication, synchronization and task scheduling overheads, this speedup increases less than linearly with the number of processors applied. The optimal scheduling problem is to determine the number of processors assigned to each task, and to the task sequencing, to minimise the finishing time. Using optimal control theory, in the special case where the speedup function of each task is p/sup /spl alpha// (where p is the amount of processing power applied to the task), a closed form solution for task graphs formed from parallel and series connections was derived. This paper considerably extends these techniques for arbitrary DAGs and applies them to matrix arithmetic compilation. The optimality conditions impose nonlinear constraints on the flow of processing power from predecessors to successors, and on the finishing times of siblings. This paper presents a fast algorithm for determining and solving these nonlinear equations. The algorithm utilizes the structure of the finishing time equations to efficiently run a conjugate gradient minimization leading to the optimal solution. The algorithm has been tested on a variety of DAGs. The results presented show that it is superior to alternative heuristic approaches.>

This paper presents a hierarchical approach for compiling macro dataflow graphs for multiprocessors with local memory. Macro dataflow graphs comprise several nodes (or macro operations) that must be executed subject to prespecified precedence constraints. Programs consisting of multiple nested loops, where the precedence constraints between the loops are known, can be viewed as macro dataflow graphs. The hierarchical compilation approach comprises a processor allocation phase followed by a partitioning phase. In the processor allocation phase, using estimated speedup functions for the macro nodes, computationally efficient techniques establish the sequencing and parallelism of macro operations for close-to-optimal run-times. The second phase partitions the computations in each macro node to maximize communication locality for the level of parallelism determined by the processor allocation phase. The same approach can also be used for programs consisting of multiple loop nests, when each of the nested loops can be characterized by a speedup function. These ideas have been implemented in a prototype structure-driven compiler, SDC, for expressions of matrix operations. The paper presents the performance of the compiler for several matrix expressions on a simulator of the Alewife multiprocessor.>

Article Generalised multiprocessor scheduling using optimal control Share on Authors: G. N. Srinivasa Prasanna Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile , Bruce R. Musicus Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MA Laboratory for Computer Science and Research Laboratory for Electronics, Massachusetts Institute of Technology, Cambridge, MAView Profile Authors Info & Claims SPAA '91: Proceedings of the third annual ACM symposium on Parallel algorithms and architecturesJune 1991 Pages 216–228https://doi.org/10.1145/113379.113399Published:01 June 1991 18citation374DownloadsMetricsTotal Citations18Total Downloads374Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access