In the resource allocation problem (RAP), the goal is to divide a given amount of a resource over a set of activities while minimizing the cost of this allocation and possibly satisfying constraints on allocations to subsets of the activities. Most solution approaches for the RAP and its extensions allow each activity to have its own cost function. However, in many applications, often the structure of the objective function is the same for each activity, and the difference between the cost functions lies in different parameter choices, such as, for example, the multiplicative factors. In this article, we introduce a new class of objective functions that captures a significant number of the objectives occurring in studied applications. These objectives are characterized by a shared structure of the cost function depending on two input parameters. We show that, given the two input parameters, there exists a solution to the RAP that is optimal for any choice of the shared structure. As a consequence, this problem reduces to the quadratic RAP, making available the vast amount of solution approaches and algorithms for the latter problem. We show the impact of our reduction result on several applications, and in particular, we improve the best-known worst-case complexity bound of two problems in vessel routing and processor scheduling from [Formula: see text] to [Formula: see text]. Summary of Contribution: The resource allocation problem (RAP) with submodular constraints and its special cases are classic problems in operations research. Because these problems are studied in many different scientific disciplines, many conceptual insights, structural properties, and solution approaches have been reinvented and rediscovered many times. The goal of this article is to reduce the amount of future reinventions and rediscoveries by bringing together these different perspectives on RAPs in a way that is accessible to researchers with different backgrounds. The article serves as an exposition on RAPs and on their wide applicability in many areas, including telecommunications, energy, and logistics. In particular, we provide tools and examples that can be used to formulate and solve problems in these areas as RAPs. To accomplish this, we make three concrete contributions. First, we provide a survey on algorithms and complexity results for RAPs and discuss several recent advances in these areas. Second, we show that many objectives for RAPs can be reduced to a (simpler) quadratic objective function, which makes available the extensive collection of fast and efficient algorithms for quadratic RAPs to solve these problems. Third, we discuss the impact that RAPs and the aforementioned reduction result can make in several application areas.

Thermal management is gaining importance since it is a promising method for increasing the reliability and lifespan of mobile devices. Although the temperature can be decreased by reducing processor speed, one must take care not to increase the processing times too much; violations of deadline constraints must be prevented. This article focuses on the tradeoff between performance and device temperature. We first analyze this tradeoff and show how to determine the optimal lower bound for the maximum temperature for a given set of jobs with known workloads and deadlines. To do so, we use a thermal model, which describes how future decisions impact temperature dynamics. Then, we introduce a processor scheduling algorithm that computes the resource allocation that achieves this lower bound. Consequently, our algorithm finds the optimal resource allocation for the purpose of minimizing the maximum processor temperature for a set of jobs with known workloads and deadlines. Our experimental validation shows that our thermal management algorithm can achieve a reduction of up to 15°C (42%) of the maximum temperature when the workload is high, where a previously proposed method achieved a reduction of up to 10°C (25%). Another advantage of our method is that it decreases the variance in the temperature profile by 16% compared to previously proposed methods.

Many multicore processors are capable of decreasing the voltage and clock frequency to save energy at the cost of an increased delay. While a large part of the theory oriented literature focuses on local dynamic voltage and frequency scaling (local DVFS), where every core's voltage and clock frequency can be set separately, this article presents an in-depth theoretical study of the more commonly available global DVFS that makes such changes for the entire chip. This article shows how to choose the optimal clock frequencies that minimize the energy for global DVFS, and it discusses the relationship between scheduling and optimal global DVFS. Formulas are given to find this optimum under time constraints, including proofs thereof. The problem of simultaneously choosing clock frequencies and a schedule that together minimize the energy consumption is discussed, and based on this a scheduling criterion is derived that implicitly assigns frequencies and minimizes energy consumption. Furthermore, this article studies the effectivity of a large class of scheduling algorithms with regard to the derived criterion, and a bound on the maximal relative deviation is given. Simulations show that with our techniques an energy reduction of 30% can be achieved with respect to state-of-the-art research.

Computers can reduce their power consumption by decreasing their speed using Dynamic Voltage and Frequency Scaling (DVFS). A form of DVFS for multicore processors is global DVFS, where the voltage and clock frequency is shared among all processor cores. Because global DVFS is efficient and cheap to implement, it is used in modern multicore processors like the IBM Power 7, ARM Cortex A9 and NVIDIA Tegra 2. This theory oriented paper discusses energy optimal DVFS algorithms for such processors. There are no known provably optimal algorithms that minimize the energy consumption of nontrivial real-time applications on a global DVFS system. Such algorithms only exist for single core systems, or for simpler application models. While many DVFS algorithms focus on tasks, this theoretical study is conceptually different and focuses on the amount of parallelism. We provide a transformation from a multicore problem to a single core problem, by using the amount of parallelism of an application. Then existing single core algorithms can be used to find the optimal solution. Furthermore, we extend an existing single core algorithm such that it takes static power into account.

A nonminimum-phase channel can always be decomposed into a minimum-phase part and an all-pass part. In our approach, called all-pass CMA, the dimensionality of the CMA algorithm has been reduced to improve blind equalization of a nonminimum-phase channel's all-pass part. The dimensionality reduction has been performed by parameterizing the CMA cost function in terms of the nonminimum-phase zero location of the all-pass part to be compensated. Currently, all-pass CMA can only compensate a single nonminimum-phase zero. However, compared to CMA, it typically provides a faster and more accurate compensation of this zero.

Dynamic Power Management (DPM) and Dynamic Voltage and Frequency Scaling (DVFS) are popular techniques for reducing energy consumption. Algorithms for optimal DVFS exist, but optimal DPM and the optimal combination of DVFS and DPM are not yet solved. In this article we use well-established models of DPM and DVFS for frame-based systems. We show that it is not sufficient—as some authors argue—to consider only individual invocations of a task. We define a schedule that also takes interactions between invocations into account and prove—in a theoretical fashion—that this schedule is optimal.

Synchronous hardware can be straight forwardly modelled as a function from input and (current) state to an updated state and output. The CλaSH compiler can translate such a transition function, described in a functional language, to synthesisable VHDL. Taking a hardware-oriented viewpoint, components can then be seen as an instantiation of such a transition function. An abstraction called Arrows is used to directly model components by combining a transition function and its state. The abstraction also provides an uniform interface for composition, without losing the referential transparency offered by a functional description. Furthermore, readability of hardware designs is increased by the use of the γ-syntax, that automatically composes components according to the Arrow interface. The advantages of the Arrow abstraction and the γ-syntax are demonstrated by means of a realistic example circuit consisting of multiple components. This is a significant extension to CλaSH and enables many high level abstractions.

CλaSH is a functional hardware description language that borrows both its syntax and semantics from the functional programming language Haskell. Polymorphism and higher-order functions provide a level of abstraction and generality that allow a circuit designer to describe circuits in a more natural way than possible with the language elements found in the traditional hardware description languages. Circuit descriptions can be translated to synthesizable VHDL using the prototype CλaSH compiler. As the circuit descriptions, simulation code, and test input are also valid Haskell, complete simulations can be done by a Haskell compiler or interpreter, allowing high-speed simulation and analysis.

Reduction circuits are used to reduce rows of floating point values to single values. Binary floating point operators often have deep pipelines, which may cause hazards when many consecutive rows have to be reduced. We present an algorithm by which any number of consecutive rows of arbitrary lengths can be reduced by a pipelined commutative and associative binary operator in an efficient manner. The algorithm is simple to implement, has a low latency, produces results in-order, and requires only small buffers. Besides, it uses only a single pipeline for the involved operation. The complexity of the algorithm depends on the depth of the pipeline, not on the length of the input rows. In this paper we discuss an implementation of this algorithm and we prove its correctness.

No abstract available.