When designing embedded systems, one needs to make decisions concerning the different components that will be included in a microprocessor. An important issue is the chip area vs. performance trade-off. In this paper the authors investigate the relationship between chip area and performance for superscalar microprocessors. The authors investigate the feasibility to obtain a suitable configuration by searching. The authors show that the approach gives a good configuration after 100 to 150 iterations using a simple random search algorithm. This shows the feasibility of the approach, in particular when more sophisticated search algorithms are employed as we plan in future work

In recent years, several approaches have been proposed to use profile information in compiler optimization. This profile information can be used at the source level to guide loop transformations as well as in the backend to guide low level optimizations. At the same time, profile guided library generators have been proposed also, like Atlas, Spiral, or FFTW, that tune their routines for the underlying hardware. These approaches have led to excellent performance improvements. However, a possible drawback of these approaches is that applications are optimized using a single or a limited set of data inputs. It is well known that programs can exhibit vastly differing behaviors for different inputs. Therefore, it is not clear whether the performance numbers reported are still valid for other input than the input used to optimize the program. In this paper, we address this problem for a specific statistical compiler tuning method. We use three different platforms and several SPECint2000 benchmarks. We show that when we tune the compiler using train data, we obtain a compiler setting that still performs well for reference data. These results suggest that profile guided optimization may be more stable than is sometimes believed and that a limited number of train data sets are sufficient to obtain a well optimized program for all inputs

Abstract Embedded systems are increasingly expected to provide good performance at low cost. As the characteristics of compiled code can have an impact on the overall cost of an embedded system, a compilation strategy must be cost aware as well as achieve high performance. As one major factor for system cost is memory size, code size becomes an important issue in code generation. Thus, cost‐effective optimization strategies that are able to perform a good trade‐off between code size and performance improvement are needed. In this paper, we propose a novel method based on Integer Linear Programming for computing efficient unroll factors for collections of loop nests with control over code size and side‐effects of the transformation. We define a notion of trade‐off between code size and performance. Experiments on the Philips Trimedia show that our method achieves excellent trade‐offs. Copyright © 2006 John Wiley & Sons, Ltd.

This special issue of Concurrency and Computation: Practice and Experience is devoted to a selection of papers presented at the 10th International Workshop on Compilers for Parallel Computers (CPC 2003), held in Amsterdam, 8-10 January 2003.During this workshop, a total of 36 papers were presented and eight of these were selected for this special issue.The goal of CPC is to bring together researchers in the compiler area in an informal atmosphere to discuss their current research and to foster collaboration.CPC was first organized in Oxford, U.K. in 1989.During that time, the workshop was focused on high-performance computing issues, such as data distribution, high-performance Fortran (HPF) and other parallel Fortran dialects, automatic parallelization, sparse matrix computations, etc.In most, if not all, of the papers Fortran was used as the source language.This remained the case for the next couple of workshops, held in Paris (1990) and Vienna (1992).To give a flavor of the changing focus of CPC, in Delft (1993) 38% of the papers dealt with HPF or some related parallel Fortran dialect.In Malaga (1995) 31% of papers did so, in Aachen (1996) 30%, in Linköping (1998) 19%, in Aussois (2000) 11%, in Edinburgh (2001) 8%, and in Amsterdam (2003) only 2%.At the same time, we have witnessed a steady increase in papers that deal with Very Long Instruction Word (VLIW), Java, Integer Linear Programming (ILP) scheduling issues, embedded systems, etc.It is safe to say that CPC is a continuously changing and adapting workshop and continues to provide a forum for present-day research.The program of the 2003 installment reflects the diverse research topics in compiler construction, ranging from 'classical' parallelizing compilers and program analysis to optimizations specific for embedded systems, performance analysis for large-scale applications and systems to automatic code generation from high-level mathematical specifications, and so on.This diversity reflects the central role the compiler is playing in the present-day computer arena.Modern systems, be they largescale supercomputers or embedded systems, require cutting-edge compiler technology for them to be efficiently programmable.The first paper in this special issue is authored by Yoshida and proposes an overlapping task assignment scheme for hierarchical coarse-grain parallel processing.This paper can be seen as a 'classical' paper on high-performance computing.

Current operating systems (OS) perceive the different contexts of simultaneous multithreaded (SMT) processors as multiple independent processing units, although, in reality, threads executed in these units compete for the same hardware resources. Furthermore, hardware resources are assigned to threads implicitly as determined by the SMT instruction fetch (Ifetch) policy, without the control of the OS. Both factors cause a lack of control over how individual threads are executed, which can frustrate the work of the job scheduler. This presents a problem for general purpose systems, where the OS job scheduler cannot enforce priorities, and also for embedded systems, where it would be difficult to guarantee worst-case execution times. In this paper, we propose a novel strategy that enables a two-way interaction between the OS and the SMT processor and allows the OS to run jobs at a certain percentage of their maximum speed, regardless of the workload in which these jobs are executed. In contrast to previous approaches, our approach enables the OS to run time-critical jobs without dedicating all internal resources to them so that non-time-critical jobs can make significant progress as well and without significantly compromising overall throughput. In fact, our mechanism, in addition to fulfilling OS requirements, achieves 90 percent of the throughput of one of the best currently known fetch policies for SMTs.

In Simultaneous Multithreaded (SMT) architectures most hardware resources are shared between threads. This provides a good cost/performance trade-off which renders these architectures suitable for use in embedded systems. However, since threads share many resources, they also interfere with each other. As a result, execution times of applications become highly unpredictable and dependent on the context in which an application is executed. Obviously, this poses problems if an SMT is to be used in a real-time system.In this paper, we propose two novel hardware mechanisms that can be used to reduce this performance variability. In contrast to previous approaches, our proposed mechanisms do not need any information beyond the information already known by traditional job schedulers. Nor do they require extensive profiling of workloads to determine optimal schedules. Our mechanisms are based on dynamic resource partitioning. The OS level job scheduler needs to be slightly adapted in order to provide the hardware resource allocator some information on how this resource partitioning needs to be done. We show that our mechanisms provide high stability for SMT architectures to be used in real-time systems: the real time benchmarks we used meet their deadlines in more than 98% of the cases considered while the other thread in the workload still achieves high throughput.

Finding nearly optimal optimization settings for modern compilers which can utilize a large number of optimizations is a combinatorially exponential problem. In this paper, we investigate whether in the presence of many optimization choices random generation of compiler settings can be used to obtain well performing compiler settings. We apply this random generation of compiler setting to gcc 3.3.1 which implements 54 optimizations. Our results show that this technique can be used to obtain a setting which exceeds the performance of the default optimization settings O1, O2, and O3 for each program in the SPECint95 benchmark suite. We also apply this technique to obtain a general setting which is suitable for many programs. This setting performs equally well as the default settings using significantly less options. Finally, we compare our setting with the default settings of gcc and analyze the difference.

In a simultaneous multithreaded (SMT) architecture, the front end of a superscalar is adapted in order to be able to fetch from several threads while the back end is shared among the threads. In this paper, we describe different resource sharing models in SMT processors. We show that explicit resource allocation can improve SMT performance. In addition, it enables SMTs to solve other QoS requirements, not realizable before.

Abstract Iterative compilation, where we search for the best program transformation based on profile feedback information, has been highly successful in determining good program optimizations, typically outperforming all static approaches. However, this benefit has come at a price, namely, a large number of executions of the target program which in many cases is unacceptable. This paper is concerned with reducing the number of program executions needed by iterative compilation by incorporating static models. We examine how static models may be incorporated into a purely iterative approach by developing several characterized heuristics. We empirically explore the tradeoff between reducing the number of executions required and the ultimate performance achieved for differing parameters or slack factors. We focus on tiling and unrolling as transformations and cache models as a test case for the feasibility of this approach. We show that a highly accurate model, used as a filter to profiling and appropriately parameterized, can reduce the number of executions by 50%. We also show that using a simple model to rank transformations and profiling, only those with the highest ranking can reduce the number of executions even further up to 70%, in cases where there is only a limited number of profiles available. We conclude that a production compiler might perform best using the last approach, gaining the benefit of iterative compilation at a much reduced cost. Copyright © 2004 John Wiley & Sons, Ltd.

This paper presents an overview of the activities carried out within the ESPRIT project OCEANS whose objective is to investigate and develop advanced compiler infrastructure for embedded VLIW processors. This combines high and low-level optimisation approaches within an iterative framework for compilation. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Primitives in mathematical software are usually written and optimized by hand. With the implementation of a “sparse compiler” that is capable of automatically converting a dense program into sparse code, however, a completely different approach to the generation of sparse primitives can be taken. A dense implementation of a particular primitive is supplied to the sparse compiler, after which it can be converted into many different sparse versions of this primitive. Each version is specifically tailored to a class of sparse matrices having a specific nonzero structure. In this article, we discuss some of our experiences with this new approach.

Article Free Access Share on Non-singular data transformations: definition, validity and applications Authors: M. F. P. O'Boyle Department of Computer Science, The University of Edinburgh, Edinburgh EH9 3JZ, United Kingdom Department of Computer Science, The University of Edinburgh, Edinburgh EH9 3JZ, United KingdomView Profile , P. M. W. Knijnenburg Department of Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The Netherlands Department of Computer Science, Leiden University, Niels Bohrweg 1, 2333 CA Leiden, The NetherlandsView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 309–316https://doi.org/10.1145/263580.263655Published:11 July 1997Publication History 32citation266DownloadsMetricsTotal Citations32Total Downloads266Last 12 Months21Last 6 weeks3 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 SiteeReaderPDF

Abstract In this paper we define a uniform language ℒ that is an extension of the language underlying the process algebra PA . One of the main extensions of this language over PA is given by so-called atomizing brackets. If we place these brackets around a statement then we treat this statement as an atomic action. Put differently, these brackets remove all interleaving points. We present a transition system for the language and derive its operational semantics. We show that there are several options for defining a transition system such that the resulting operational semantics is a conservative extension of the semantics for PA . We define a semantic domain and a denotational model for the language. Next we define a closure operator on the semantic domain and show how to use this closure operator to derive a fully abstract denotational semantics. Then the algebraic theory of the language is considered. We define a collection of axioms and a term rewrite system based on these axioms. Using this term rewrite system we are able to identify normal forms for the language. It is shown that these axioms capture the denotational equality. It follows that if two terms are provably equal then they have the same operational semantics. Finally, we show how to extend the axiomatization in order to axiomatize its operational equivalence.

this paper we define a different representation for the Smyth powerdomain. We use minimal representatives instead of maximal ones. The reason for using minimal representatives is the following. Consider the collection of all possible results of a nondeterministic program. The worst case behaviour of this program is precisely captured by the minimal elements in this collection. The Smyth powerdomain identifies programs with the same collection of minimal elements in their denotation and hence can be used for modelling worst case behaviour. Hence it is desirable to represent the Smyth powerdomain as a collection of sets of minimal elements together with an ordering relation, and to show how functions on this representation can be defined. In this way, 1

In this paper we provide a categorical interpretation of the first-order Hoare logic of a small programming language by giving a weakest precondition semantics for the language. To this end, we extend the well-known notion of a (first-order) hyperdoctrine to include partial maps. The most important new aspect of the resulting partial (first-order) hyperdoctrine is a different notion of morphism between the fibres. We also use this partial hyperdoctrine to give a model for Beeson's Partial Function Logic such that (a version of) his axiomatization is complete with respect to this model. This shows the usefulness of the notion, independent of its intended use as a model for Hoare logic.