Summary This paper presents an extended version of Deeper, a search‐based simulation‐integrated test solution that generates failure‐revealing test scenarios for testing a deep neural network‐based lane‐keeping system. In the newly proposed version, we utilize a new set of bio‐inspired search algorithms, genetic algorithm (GA), and evolution strategies (ES), and particle swarm optimization (PSO), that leverage a quality population seed and domain‐specific crossover and mutation operations tailored for the presentation model used for modeling the test scenarios. In order to demonstrate the capabilities of the new test generators within Deeper, we carry out an empirical evaluation and comparison with regard to the results of five participating tools in the cyber‐physical systems testing competition at SBST 2021. Our evaluation shows the newly proposed test generators in Deeper not only represent a considerable improvement on the previous version but also prove to be effective and efficient in provoking a considerable number of diverse failure‐revealing test scenarios for testing an ML‐driven lane‐keeping system. They can trigger several failures while promoting test scenario diversity, under a limited test time budget, high target failure severity, and strict speed limit constraints.

Many program analysis techniques depend on capturing the control dependencies of the program. Most existing control dependence algorithms either compute intraprocedural control dependencies only, or they compute control dependence relations that are not precise in general including nonterminating systems. Weak control closure (WCC) subsumes all known nontermination insensitive control dependence relations, including those that are appropriate for nonterminating systems. In this paper, we provide the first formal development of an algorithm to compute the WCC for interprocedural programs capturing the weak form of interprocedural control dependencies. The method is widely applicable due to the generality of WCC. Theorems on the theoretical results of soundness, precision, and the worst-case complexity of our method are also included. We have compared our algorithm with a WCC computation algorithm based on a state-of-the-art interprocedural control dependence computation algorithm. The latter algorithm loses soundness, and we improve the precision by 15.21% on all our experimental benchmarks. This empirical evidence suggests that our algorithm is more effective for any client application of WCC requiring interprocedural program analysis.

In recent years, maintaining test code quality has gained more attention due to increased automation and the growing focus on issues caused during this process.Test code may become long and complex, but maintaining its quality is mostly a manual process, that may not scale in big software projects. Moreover, bugs in test code may give a false impression about the correctness or performance of the production code. Static program analysis (SPA) tools are being used to maintain the quality of software projects nowadays. However, these tools are either not used to analyse test code, or any analysis results on the test code are suppressed.This is especially true since SPA tools are not tailored to generate precise warnings on test code. This paper investigates the use of SPA on test code by employing three state-of-the-art general-purpose static analysers on a curated set of projects used in the industry and a random sample of relatively popular and large open-source C/C++ projects. We have found a number of built-in code checking modules that can detect quality issues in the test code. However, these checkers need some tailoring to obtain relevant results. We observed design choices in test frameworks that raise noisy warnings in analysers and propose a set of augmentations to the checkers or the analysis framework to obtain precise warnings from static analysers.

Abstract Test automation brings the potential to reduce costs and human effort, but several aspects of software testing remain challenging to automate. One such example is automated performance testing to find performance breaking points. Current approaches to tackle automated generation of performance test cases mainly involve using source code or system model analysis or use-case-based techniques. However, source code and system models might not always be available at testing time. On the other hand, if the optimal performance testing policy for the intended objective in a testing process instead could be learned by the testing system, then test automation without advanced performance models could be possible. Furthermore, the learned policy could later be reused for similar software systems under test, thus leading to higher test efficiency. We propose SaFReL, a self-adaptive fuzzy reinforcement learning-based performance testing framework. SaFReL learns the optimal policy to generate performance test cases through an initial learning phase, then reuses it during a transfer learning phase, while keeping the learning running and updating the policy in the long term. Through multiple experiments in a simulated performance testing setup, we demonstrate that our approach generates the target performance test cases for different programs more efficiently than a typical testing process and performs adaptively without access to source code and performance models.

Performance testing with the aim of generating an efficient and effective workload to identify performance issues is challenging. Many of the automated approaches mainly rely on analyzing system models, source code, or extracting the usage pattern of the system during the execution. However, such information and artifacts are not always available. Moreover, all the transactions within a generated workload do not impact the performance of the system the same way, a finely tuned workload could accomplish the test objective in an efficient way. Model-free reinforcement learning is widely used for finding the optimal behavior to accomplish an objective in many decision-making problems without relying on a model of the system. This paper proposes that if the optimal policy (way) for generating test workload to meet a test objective can be learned by a test agent, then efficient test automation would be possible without relying on system models or source code. We present a self-adaptive reinforcement learning-driven load testing agent, RELOAD, that learns the optimal policy for test workload generation and generates an effective workload efficiently to meet the test objective. Once the agent learns the optimal policy, it can reuse the learned policy in subsequent testing activities. Our experiments show that the proposed intelligent load test agent can accomplish the test objective with lower test cost compared to common load testing procedures, and results in higher test efficiency.

Existing proofs of correctness for dependence-based slicing methods are limited either to the slicing of intraprocedural programs [2, 39], or the proof is only applicable to a specific slicing method [4, 41]. We contribute a general proof of correctness for dependence-based slicing methods such as Weiser [50, 51], or Binkley et al. [7, 8], for interprocedural, possibly nonterminating programs. The proof uses well-formed weak and strong control closure relations, which are the interprocedural extensions of the generalised weak/strong control closure provided by Danicic et al. [13], capturing various nonterminating-insensitive and nontermination-sensitive control-dependence relations that have been proposed in the literature. Thus, our proof framework is valid for a whole range of existing control-dependence relations. We have provided a definition of semantically correct (SC) slice. We prove that SC slices agree with Weiser slicing, that deterministic SC slices preserve termination, and that nondeterministic SC slices preserve the nondeterministic behavior of the original programs.

In the past, assertions were mostly used to validate the system through the design and simulation process. Later, a new method known as assertion synthesis was introduced, which enabled the designers to use the assertions for high-speed hardware emulation and safety and reliability insurance after tape-out. Although the synthesis of the assertions at the register transfer level is proposed and implemented in several works, none of them can be adopted for high-level assertions. In this paper, we propose the SHiLA framework and a detailed implementation guide by which assertion synthesis can also be applied to the high-level design processes. The proposed method, which is fully tool independent, is not only an enabler to highspeed assertion-assisted simulation but can also be used in other scenarios that need assertion synthesis, as it has the minimum possible effect on the main design's performance.

Self-healing is a promising approach for designing reliable digital systems. It refers to the ability of a system to detect faults and automatically fixing them to avoid total failure. With the development of digital systems, heterogeneous systems, in which some parts of the system are executed on the programmable logic, and some other parts run on the processing elements (CPU), are becoming more prevalent. In this work, we propose an adjustable self-healing method that is applicable to heterogeneous systems with accelerated functions and enables the designers to add the self-healing feature to the design. In this method, by manipulating the software codes that are being executed on the processing element, we add the ability to verify the accelerated functions on the programmable logic and heal the possible failures to the system. This is done not only in a straightforward manner but also without being forced to choose a specific reliability-overhead point. The designer will have the option to select the optimum configuration for a desired reliability level. Experimental results on a large design including several accelerated functions are provided and show 42% improvement of reliability by having 27% overhead, as an example of the reliability-overhead point.

Performance testing remains a challenge, particularly for complex systems. Different application-, platform- and workload-based factors can influence the performance of software under test. Common approaches for generating platform- and workload-based test conditions are often based on system model or source code analysis, real usage modeling and use-case based design techniques. Nonetheless, creating a detailed performance model is often difficult, and also those artifacts might not be always available during the testing. On the other hand, test automation solutions such as automated test case generation can enable effort and cost reduction with the potential to improve the intended test criteria coverage. Furthermore, if the optimal way (policy) to generate test cases can be learnt by testing system, then the learnt policy can be reused in further testing situations such as testing variants, evolved versions of software, and different testing scenarios. This capability can lead to additional cost and computation time saving in the testing process. In this research, we present an autonomous performance testing framework which uses a model-free reinforcement learning augmented by fuzzy logic and self-adaptive strategies. It is able to learn the optimal policy to generate platform- and workload-based test conditions which result in meeting the intended testing objective without access to system model and source code. The use of fuzzy logic and self-adaptive strategy helps to tackle the issue of uncertainty and improve the accuracy and adaptivity of the proposed learning. Our evaluation experiments show that the proposed autonomous performance testing framework is able to generate the test conditions efficiently and in a way adaptive to varying testing situations.

Hardware manufacturers are forced to improve system performance continuously due to advanced and computationally demanding system functions. Unfortunately - more powerful hardware leads to increased costs. Instead, companies attempt to improve performance by consolidating multiple functions to share the same hardware to exploit existing performance instead. In legacy systems, each function had individual execution environment that guaranteed HW resource isolation and therefore the Quality of Service (QoS). Consolidation of multiple functions increases the risk of shared resource congestion. Current process schedulers focus on time quanta and do not consider shared resources. We present a novel process scheduler that complements current process schedulers by enforcing QoS though Shared Resource Aware (SRA) process scheduling. The SRA scheduler programs the Performance Monitoring Unit (PMU) to generate an overflow interrupt when reaching the assigned process resource quota. The scheduler has the possibility to swap out the process when receiving the interrupt allowing it to enforce the QoS for the scheduled process. We have implemented our scheduling policy as a new scheduling class in Linux. Our experiments show that it efficiently enforces QoS without seriously affect the shared resource usage of other processes executing on the same HW.

One of the major advantages of Model-Driven Engineering is the possibility to early assess crucial system properties, in order to identify issues that are easier and cheaper to solve at design level than at code level. An example of such a property is the timing behaviour of a real-time application, where an early indication that the timing constraints might not be met can help avoiding costly re-designs late in the development process. In this paper we provide a model-driven round-trip transformation chain for (i) applying a flow analysis to executable models described in terms of the Action Language for Foundational UML (AU), and (ii) back-propagating analysis results to Alf models for further investigation. Alf models are transformed into the input format for an analysis tool that identifies flow facts, i.e., information about loop bounds and infeasible paths in the model. Flow facts can be used, for instance, when estimating the worst-case execution time for the analysed model. We evaluated the approach through a set of benchmark models of various size and complexity.

Program slicing identifies the program parts that may affect certain properties of the program, such as the outcomes of conditions affecting the program flow. Ottenstein's Program Dependence Graph (PDG) based algorithm is the state-of-practice for static slicing today: it is well-suited in applications where many slices are computed, since the cost of building the PDG then can be amortized over the slices. But there are applications that require few slices of a given program, and where computing all the dependencies may be unnecessary. We present a light-weight interprocedural algorithm for backward static slicing where the data dependence analysis is done using a variant of the Strongly Live Variables (SLV) analysis. This allows us to avoid building the Data Dependence Graph, and to slice program statements "on-the-fly'' during the SLV analysis which is potentially faster for computing few slices. Furthermore we use an abstract interpretation-based value analysis to extend our slicing algorithm to slice low-level code, where data dependencies are not evident due to dynamically calculated addresses. Our algorithm computes slices as sets of Control Flow Graph nodes: we show how to adapt existing techniques to generate executable slices that correspond to semantically correct code, where jump statements have been inserted at appropriate places. We have implemented our slicing algorithms, and made an experimental evaluation comparing them with the standard PDG-based algorithm for a number of example programs. We obtain the same accuracy as for PDG-based slicing, sometimes with substantial improvements in performance.

Communication is a vital part of computer systems today. One current problem is that computational capacity is growing faster than the bandwidth of interconnected computers. Maximising performance is a key objective for industries, both on new and existing software systems, which further extends the need for more powerful systems at the cost of additional communication. Our contribution is to let the system selectively choose the best compression algorithm from a set of available algorithms if it provides a better overall system performance. The online selection mechanism can adapt to a changing environment such as temporary network congestion or a change of message content while still selecting the optimal algorithm. Additionally, is autonomous and does not require any human intervention making it suitable for large-scale systems. We have implemented and evaluated this autonomous selection and compression mechanism in an initial trial situation as a proof of concept. The message round trip time were decreased by 7.1%, while still providing ample computational resources for other co-existing services.

An AUTOSAR-based software application contains a set of software components, each of which encapsulates a set of runnable entities. In fact, the mission of the system is fulfilled as result of the collaboration between the runnables. Several trends have recently emerged to utilize multi-core technology to run AUTOSAR-based software. Not only the overhead of communication between the runnables is one of the major performance bottlenecks in multi-core processors but it is also the main source of unpredictability in the system. Appropriate mapping of the runnables onto a set of tasks (called mapping process) along with proper allocation of the tasks to processing cores (called task allocation process) can significantly reduce the communication overhead. In this paper, three solutions are suggested, each of which comprises both the mapping and the allocation processes. The goal is to maximize key performance aspects by reducing the overall inter-runnable communication time besides satisfying given timing and precedence constraints. A large number of randomly generated experiments are carried out to demonstrate the efficiency of the proposed solutions.

Multi-core technology is recognized as a key component to develop new cost-efficient products. It can lead to reduction of the overall hardware cost through hardware consolidation. However, it also results in tremendous challenges related to the combination of predictability and performance. The AUTOSAR consortium has developed as the worldwide standard for automotive embedded software systems. One of the prominent aspects of this consortium is to support multi-core systems. In this paper, the ongoing work on addressing the challenge of achieving a resource efficient and predictable mapping of AUTOSAR runnables onto a multi-core system is discussed. The goal is to minimize the runnables' communication cost besides meeting timing and precedence constraints of the runnables. The basic notion utilized in this research is to consider runnable granularity, which leads to an increased flexibility in allocating runnables to various cores, compared of task granularity in which all of the runnables hosted on a task should be allocated on the same core. This increased flexibility can potentially enhance communication cost. In addition, a heuristic algorithm is introduced to create a task set according to the mapping of runnables on the cores. In our current work, we are formulating the problem as an Integer Linear Programming (ILP). Therefore, conventional ILP solvers can be easily applied to derive a solution.

Embedded systems are often business- or safety-critical, with strict timing requirements that have to be met for the information-processing. Code-level timing analysis (used to analyse software running on some given hardware w.r.t. its timing properties) is an indispensable technique for ascertaining whether or not these requirements are met. However, recent developments in hardware, especially multi-core processors, and in software organisation render analysis increasingly more difficult, thus challenging the evolution of timing analysis techniques. This special session aims to give an overview over the current state of the art and the future challenges w.r.t. code-level timing analysis and introduces TACLe, a recently started EU-funded networking activity targeting these challenges.

Worst-Case Execution Time (WCET) analysis derives upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. Static WCET analysis derives safe upper bounds. For complex hardware architectures the hardware modelling is still a challenge, leading to long analysis times and a risk of large WCET overestimation. Therefore, hybrid WCET analysis methods have appeared, where measurements are used to augment or replace the detailed low-level static WCET analysis. These methods do not in general yield a safe WCET estimate, but can still be appropriate in soft real-time systems where such WCET estimates are not crucial. In this paper we make two contributions. First, we develop a hybrid WCET analysis method, which uses regression to identify parameters in the common linear Implicit Path Enumeration Technique (IPET) model for WCET calculation. The method can use timing measurements of different granularity, including end-to-end measurements, which reduces the need for fine-grained timing measurement instrumentation. It uses a novel kind of regression, which guarantees that the identified model does not underestimate any observed execution times. Second, we initiate the development of an IPET-based theory for hybrid WCET analysis test coverage, and we formulate and prove a coverage criterion for the tests needed to identify a safe model.

Static WCET analysis is a process dedicated to derive a safe upper bound of the worst-case execution time of a program. In many real-time systems, however, a constant global WCET estimate is not always so useful since a program may behave very differently depending on its configuration or mode. A parametric WCET analysis derives the upper bound as formula rather than a constant. This paper presents a new efficient algorithm that can obtain a safe parametric estimate of the WCET of a program. This algorithm is evaluated on a large set of benchmarks and compared to a previous approach to parametric WCET calculation. The evaluation shows that the new algorithm, to the cost of some imprecision, scales much better and can handle more realistic programs than the previous approach.

A static worst-case execution time (WCET) analysis derives upper bounds for the execution times of programs. Such analysis requires information about the possible program flows. The current practice is to provide this information manually, which can be laborious and error-prone. An alternative is to derive this information through an automated flows analysis.In this article, we present a case study where an automatic flows analysis method was tested on industrial real-time system code. The same code was the subject of an earlier WCET case study, where it was analysed using manual annotations for the flows information. The purpose of the current study was to see to which extent the same flows information could be found automatically. The results show that for the most part this is indeed possible, and we could derive comparable WCET estimates using the automatically generated flow information. In addition, valuable insights were gained on what is needed to make flow analysis methods work on real production code.

Hard real-time systems have stringent timing constraints expressed in units of time. To ensure that a task finishes within its time-frame, the designer of sucha system must be able to derive upper bounds on the task's worst-case execution time (WCET). To compute such upper bounds, timing analyses are used. These analyses require that information such as bounds on the maximum numbers of loop iterations are known statically, i.e. during design time. Parametric timing analysis softens these requirements: it yields symbolic formulas instead of single numeric values representing the upper bound on the task's execution time. In this paper, we present a new parametric timing analysis that is able to derive safe and precise results. Our method determines what the parameters ofthe program are, constructs parametric loop bounds, takes processor behavior into account and attains a formula automatically. In the end, we present tests to show that the precision and runtime of our analysis are very close to those of numeric timing analysis.

Caches have become increasingly important with the widening gap between main memory and processor speeds. Small and fast cache memories are designed to bridge this discrepancy. However, they are only effective when programs exhibit sufficient data locality. In addition, caches are a source of unpredictability, resulting in programs sometimes behaving in a different way than expected. Detailed information about the number of cache misses and their causes allows us to predict cache behavior and to detect bottlenecks. Small modifications in the source code may change memory patterns, thereby altering the cache behavior. Code transformations, which take the cache behavior into account, might result in a high cache performance improvement. However, cache memory behavior is very hard to predict, thus making the task of optimizing and timing cache behavior very difficult. This article proposes and evaluates a new compiler framework that times cache behavior for multitasking systems. Our method explores the use of cache partitioning and dynamic cache locking to provide worst-case performance estimates in a safe and tight way for multitasking systems. We use cache partitioning, which divides the cache among tasks to eliminate intertask cache interferences. We combine static cache analysis and cache-locking mechanisms to ensure that all intratask conflicts, and consequently, memory access times, are exactly predictable. The results of our experiments demonstrate the capability of our framework to describe cache behavior at compile time. We compare our timing approach with a system equipped with a nonpartitioned, but statically, locked data cache. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, demonstrating that our fully predictable scheme does not compromise the performance of the transformed programs.

Methods for worst-case execution time (WCET) analysis have been known for some time, and recently commercial tools have emerged. This technique is gradually being entered into industry to analyse real production codes. This article presents a case study where the aiT WCET analysis tool was used to find upper time bounds for task-oriented vehicular control code. The main purpose was to investigate the practical difficulties that arise when applying the current WCET analysis methods to this particular kind of code. In particular, we were interested in how labor-intense the analysis becomes, measured by the number of manual annotations necessary for calculating a WCET estimate. We were also interested how much tighter WCET estimates will become by manually adding extra annotations, and how much additional work that is needed to give these annotations. We also made some systematic comparisons between calculated and measured WCET estimates for the analysed system.

Static Worst-Case Execution Time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. WCET analysis needs a program flow analysis to derive constraints on the possible execution paths of the analysed program, like iteration bounds for loops and dependences between conditionals.Current WCET analysis tools typically obtain flow information through manual annotations. Better support for automatic flow analysis would eliminate much of the need for this laborious work. However, to automatically derive high-quality flow information is hard, and solution techniques with large time and space complexity are often required.In this paper we describe how to use program slicing to reduce the computational need of flow analysis methods. The slicing identifes statements and variables which are guaranteed not to influence the program flow. When these are removed, the calculation time of our different flow analyses decreases, in some cases considerably.We also show how program slicing can be used to identify the input variables and globals that control the outcome of a particular loop or conditional. This should be valuable aid when performing WCET analysis and systematic testing of large and complex real-time programs.

Static worst-case execution time (WCET) analysis is a technique to derive upper bounds for the execution times of programs. Such bounds are crucial when designing and verifying real-time systems. A key component for statically deriving safe and tight WCET bounds is information on the possible program flow through the program. Such flow information can be provided manually by user annotations, or automatically by a flow analysis. To make WCET analysis as simple and safe as possible, it should preferably be automatically derived, with no or very limited user interaction. In this paper we present a method for deriving such flow information called abstract execution. This method can automatically calculate loop bounds, bounds for including nested loops, as well as many types of infeasible paths. Our evaluations show that it can calculate WCET estimates automatically, without any user annotations, for a range of benchmark programs, and that our techniques for nested loops and infeasible paths sometimes can give substantially better WCET estimates than using loop bounds analysis only

The number of embedded computers used in modern cars have increased dramatically during the last years, as they provide increased functionality to a reduced cost compared to previous technologies. These computers are often connected by one or more communication networks and the data traffic sent over the networks often has hard real-time requirements. To provide overall system timing guarantees, upper timing bounds need to be derived both for the data traffic and the embedded computer programs that controls the communication. In this article, we present a case study where static worst-case execution time (WCET) analysis was used to find upper time bounds for time-critical code in products from Volcano Communications Technologies AB (VCT). The VCT company provides tools for development of real-time communication solutions for embedded network systems, mainly used within the car industry. VCT's tool suite includes support for Controller Area Network (CAN), Local Interconnect Network (LIN), FlexRay and MOST network traffic. The primary purpose of the study was not to test the accuracy of the obtained WCET estimates, but rather to investigate the practical difficulties that arise when applying current WCET analysis methods to these particular kind of systems. A central question was if today is static WCET analysis tools can be used in the automotive software development process. In particular, we were interested in how labor-intensive the analysis becomes, measured by the number of manual annotations necessary to perform the analysis. As a result, we provide some qualitative observations on desirable research results for making static WCET analysis applicable in typical automotive software development.

In reactive systems, execution is driven by external events to which the system should respond with appropriate actions. Such events can be simple, but systems are often supposed to react to sophisticated situations involving a number of simpler events occurring in accordance with some pattern. A systematic approach to handle this type of systems is to separate the mechanism for detecting composite events from the rest of the application logic.In this paper, we present an event algebra for composite event detection. We show a number of algebraic laws that facilitate formal reasoning, and justify the algebra semantics by showing to what extent the operators comply with intuition. Finally, we present an implementation of the algebra, and identify a large subset of expressions for which detection can be performed with bounded resources.

Data caches are essential in modern processors, bridging the widening gap between main memory and processor speeds. However, they yield very complex performance models, which make it hard to bound execution times tightly. This paper contributes a new technique to obtain predictability in preemptive multitasking systems in the presence of data caches. We explore the use of cache partitioning, dynamic cache locking, and static cache analysis to provide worst-case performance estimates in a safe and tight way. Cache partitioning divides the cache among tasks to eliminate inter-task cache interferences. We combine static cache analysis and cache locking mechanisms to ensure that all intra-task conflicts, and consequently, memory access times, are exactly predictable. To minimize the performance degradation due to cache partitioning and locking, two strategies are employed. First, the cache is loaded with data likely to be accessed so that their cache utilization is maximized. Second, compiler optimizations such as tiling and padding are applied in order to reduce cache replacement misses. Experimental results show that this scheme is fully predictable, without compromising the performance of the transformed programs. Our method outperforms static cache locking for all analyzed task sets under various cache architectures, with a CPU utilization reduction ranging between 3.8 and 20.0 times for a high performance system.

Caches have become increasingly important with the widening gap between main memory and processor speeds. However, they are a source of unpredictability due to their characteristics, resulting in programs behaving in a different way than expected.Cache locking mechanisms adapt caches to the needs of real-time systems. Locking the cache is a solution that trades performance for predictability: at a cost of generally lower performance, the time of accessing the memory becomes predictable.This paper combines compile-time cache analysis with data cache locking to estimate the worst-case memory performance (WCMP) in a safe, tight and fast way. In order to get predictable cache behavior, we first lock the cache for those parts of the code where the static analysis fails. To minimize the performance degradation, our method loads the cache, if necessary, with data likely to be accessed.Experimental results show that this scheme is fully predictable, without compromising the performance of the transformed program. When compared to an algorithm that assumes compulsory misses when the state of the cache is unknown, our approach eliminates all overestimation for the set of benchmarks, giving an exact WCMP of the transformed program without any significant decrease in performance.

Abstract Unfolding is a common technique in program transformations. Here, we present a computation model where unfolding is a simple generalisation of the usual concept of evaluation. The model is a variant of the well-known full substitution evaluation rule for recursive programs. The evaluation mechanism involved is symbolic substitution of function definitions followed by simplification. Simplification is expressed as a confluent rewrite strategy which uses three kinds of reductions: β-reduction, non-erasing reduction, and erasing reduction. Non-erasing reductions include simplification of constant subexpressions. Erasing reductions formalize the behaviour of nonstrict operations. In this computation model, we prove a termination theorem of symbolic unfolding relative to more instantiated calls. A possible application of the model is a technique called total unfolding , where a partially instantiated function call is unfolded until no more calls exist. Under certain conditions the result will be a first order term: such terms correspond to basic blocks in imperative programs and can be efficiently implemented by scheduling techniques. Possible applications are hardware synthesis, and code generation for parallel machines.

Static algorithmsare such algorithms whose behaviour is independent of indata.Regardless of the input, the same computations will always be carried out.Because of this property, static algorithms can be scheduled once and for all, and very efficient hardware with a minimum of control can be designed to support the schedule.Machinery.

Many regular algorithms, suitable for VLSI implementation, are naturally described by sets of integer index vectors together with a rule that assigns a computation to each vector.Regular VLSI structures for such algorithms can be found by mapping the index vectors to a discrete space-time with integer coordinates.If the scope is restricted to linear or affine mappings, then the minimization of the execution time for the VLSI implementation with respect to the space-time mapping is essentially an integer linear programming (ILP) problem.If the entries in the vector describing the time function must be integers, ILP techniques can be applied directly.There are, however, index sets that allow space-time mappings with rational, non-integral entries.In such cases, ILP will not consider all possible affine time functions and an optimal solution ma.y go unnoticed.In this paper we give sufficient conditions on the index set, for when integer time functions are allowed only.We also give a general algorithm to find a "preconditioning" affine transformation of the index set, such that the transformed index set allows only integer time functions.ILP methods can then be used to find time-optimal architectures for the transformed a.lgorithm.This considerably extends the class of algorithms for which time-optimal VLSI structures can be found.