Describes an approach to the problem of optimizing memory resource use in high-performance scalable computing systems. The approach is automatic and applicable to a wide variety of system architectures. It consists of...
详细信息
Describes an approach to the problem of optimizing memory resource use in high-performance scalable computing systems. The approach is automatic and applicable to a wide variety of system architectures. It consists of a hybrid genetic algorithm optimizer (the Embedded Genetic Allocator or EGA), coupled with a high-precision softwareperformance monitoring system. EGA requires no programmer knowledge of the underlying non-uniform memory access (NUMA) architecture of the target hardware; the programmer simply specifies the data buffers to be allocated and requires that certain groups of buffers share the same performance quality. EGA minimizes the execution time of time-critical portions of the target system by allocating target program data buffers to various memory banks in the NUMA architecture. These trial allocations are loaded and evaluated directly on the target hardware. Measurements of process execution time are derived from synchronized event logging of multiple processors performed by BBN TraceMaker/sup TM/. The timing data provides the information for an optimizer cost function which the genetic algorithm uses when selecting from amongst competing allocations. Thus, EGA automates the trial-and-error method of hand optimization. We have demonstrated EGA performing memory allocation optimizations on a typical VME-based multiprocessor DSP system and completed a set of optimization experiments. The results demonstrate that EGA can be used to optimize the memory allocation on a DSP with real-world code, and that the resulting optimizations can rival those generated manually by a skilled programmer.
The problem of constructing a nonlinear controller for a biped robot optimal with respect to a minimal energy performance criteria is considered. The solution of this difficult, highly nonlinear problem is facilitated...
详细信息
The problem of constructing a nonlinear controller for a biped robot optimal with respect to a minimal energy performance criteria is considered. The solution of this difficult, highly nonlinear problem is facilitated by the conjunction of several new developments in numerical optimal control and constrained recursive dynamic models for robotic systems. A 5-link biped model is used with the full dynamics and a uniform distribution of mass at each link. Contacts are modeled as inelastic, and the full dynamics together with the contact and collision forces are calculated efficiently using a recursive symbolic representation of the dynamics. The flexibility and modularity of our dynamics algorithms allows one to construct reduced unconstrained models which do not suffer from integration difficulties. The numerical optimal control software used is powerful and quick enough to handle high dimensional nonlinear systems. The result of our experiment is a walking controller which is optimal with respect to a type of minimum energy performance.
As the amount of data transmitted over a network increases and high bandwidth applications requiring point to multipoint communications like videoconferencing, distributed database management or cooperative work becom...
详细信息
As the amount of data transmitted over a network increases and high bandwidth applications requiring point to multipoint communications like videoconferencing, distributed database management or cooperative work become widespread, it becomes very important to optimize network resources. One such optimization is multicast tree generation. The problem of generating a minimum cost multicast tree given the network topology and costs associated with the connecting links can be modelled as a Steiner tree problem which is NP-complete. Much work has been done in the direction of obtaining near-optimal multicast trees when the objective is only to minimize the cost. However, many real time applications such as videoconferencing require that data be sent within prespecified delay limits in order to avoid problems such as anachronism and lack of synchronization. We deal with the delay-bounded cost-optimal multicast tree (DBCPAT) generation problem. Specifically, we discuss a closely related problem which is to find a delay-bounded cost-optimal path (DBCP) between a specified source and destination node. Such a path can be used as a starting point to solve the DBCMT. We present an exact solution to the DBCP which is based on the branch-and-bound paradigm. We also propose a heuristic technique to solve the DBCP using the principle of evolutionary computing. The results obtained using the two techniques are compared for several large networks.
The facility layout problem (FLP) has many practical applications and is known to be NP-hard. During recent decades exact and heuristic approaches have been proposed in the literature to solve FLPs. In this paper we r...
详细信息
The facility layout problem (FLP) has many practical applications and is known to be NP-hard. During recent decades exact and heuristic approaches have been proposed in the literature to solve FLPs. In this paper we review the most recent developments regarding simulated annealing and genetic algorithms for solving facility layout problems approximately.
Numerical and computational aspects of direct methods for large and sparse least squares problems are considered. After a brief survey of the most often used methods, we summarize the important conclusions made from a...
详细信息
Numerical and computational aspects of direct methods for large and sparse least squares problems are considered. After a brief survey of the most often used methods, we summarize the important conclusions made from a numerical comparison in MATLAB. Significantly improved algorithms have during the last 10-15 years made sparse QR factorization attractive, and competitive to previously recommended alternatives. Of particular importance is the multifrontal approach, characterized by low fill-in, dense subproblems and naturally implemented parallelism. We describe a Householder multifrontal scheme and its implementation on sequential and parallel computers. Available software has in practice a great influence on the choice of numerical algorithms. Less appropriate algorithms are thus often used solely because of existing software packages. We briefly survey software packages for the solution of sparse linear least squares problems. Finally, we focus on various applications from optimization, leading to the solution of large and sparse linear least squares problems. In particular, we concentrate on the important case where the coefficient matrix is a fixed general sparse matrix with a variable diagonal matrix below. Inner point methods for constrained linear least squares problems give, for example, rise to such subproblems. Important gains can be made by taking advantage of structure. Closely related is also the choice of numerical method for these subproblems. We discuss why the less accurate normal equations tend to be sufficient in many applications.
Recently, in [12] a very general class of truncated Newton methods has been proposed for solving large scale unconstrained optimization problems. In this work we present the results of an extensive numerical experienc...
详细信息
Recently, in [12] a very general class of truncated Newton methods has been proposed for solving large scale unconstrained optimization problems. In this work we present the results of an extensive numerical experience obtained by different algorithms which belong to the preceding class. This numerical study, besides investigating which are the best algorithmic choices of the proposed approach, clarifies some significant points which underlies every truncated Newton based algorithm.
We present a computationally efficient implementation of an interior point algorithm for solving large-scale problems arising in stochastic linear programming and robust optimization. A matrix factorization procedure ...
详细信息
We present a computationally efficient implementation of an interior point algorithm for solving large-scale problems arising in stochastic linear programming and robust optimization. A matrix factorization procedure is employed that exploits the structure of the constraint matrix, and it is implemented on parallel computers. The implementation is perfectly scalable. Extensive computational results are reported for a library of standard test problems from stochastic linear programming, and also for robust optimization formulations. The results show that the codes are efficient and stable for problems with thousands of scenarios. Test problems with 130 thousand scenarios, and a deterministic equivalent linear programming formulation with 2.6 million constraints and 18.2 million variables, are solved successfully.
This paper considers the number of inner iterations required per outer iteration for the algorithm proposed by Conn er al. [9]. We show that asymptotically, under suitable reasonable assumptions, a single inner iterat...
详细信息
This paper considers the number of inner iterations required per outer iteration for the algorithm proposed by Conn er al. [9]. We show that asymptotically, under suitable reasonable assumptions, a single inner iteration suffices.
ELSO is an environment for the solution of large-scale optimization problems. With ELSO the user is required to provide only code for the evaluation of a partially separable function. ELSO exploits the partial separab...
详细信息
ELSO is an environment for the solution of large-scale optimization problems. With ELSO the user is required to provide only code for the evaluation of a partially separable function. ELSO exploits the partial separability structure of the function to compute the gradient efficiently using automatic differentiation. We demonstrate ELSO's efficiency by comparing the various options available in ELSO. Our conclusion is that the hybrid option in ELSO provides performance comparable to the hand-coded option, while having the significant advantage of not requiring a hand-coded gradient or the sparsity pattern of the partially separable function. In our test problems, which have carefully coded gradients, the computing time for the hybrid AD option is within a factor of two of the hand-coded option.
Sequential quadratic (SQP) programming methods are the method of choice when solving small or medium-sized problems. Since they are complex methods they are difficult (but not impossible) to adapt to solve large-scale...
详细信息
Sequential quadratic (SQP) programming methods are the method of choice when solving small or medium-sized problems. Since they are complex methods they are difficult (but not impossible) to adapt to solve large-scale problems. We start by discussing the difficulties that need to be addressed and then describe some general ideas that may be used to resolve these difficulties. A number of SQP codes have been written to solve specific applications and there is a general purposed SQP code called SNOPT, which is intended for general applications of a particular type. These are described briefly together with the ideas on which they are based. Finally we discuss new work on developing SQP methods using explicit second derivatives.
暂无评论