Search

This article presents a unification of previously separate actions--design and optimization--into neural architecture search (NAS) as program transformation exploration for deep neural network performance improvement. The article provides an overview of different types of convolution and transformations and how NAS operations can be expressed as transformation. This research introduces a new safety metric based on Fisher Potential and ultimately the unified framework is tested in TVM, an open source deep learning compiler.

This paper introduces DIAMetrics: a novel framework for end-to-end benchmarking and performance monitoring of query engines. DIAMetrics consists of a number of components supporting tasks such as automated workload summarization, data anonymization, benchmark execution, monitoring, regression identification, and alerting. The architecture of DIAMetrics is highly modular and supports multiple systems by abstracting their implementation details and relying on common canonical formats and pluggable software drivers. The end result is a powerful unified framework that is capable of supporting every aspect of benchmarking production systems and workloads. DIAMetrics has been developed in Google and is being used to benchmark various internal query engines. In this paper, we give an overview of DIAMetrics and discuss its design and implementation. Furthermore, we provide details about its deployment and example use cases. Given the variety of supported systems and use cases within Google, we argue that its core concepts can be used more widely to enable comparative end-to-end benchmarking in other industrial environments. [ABSTRACT FROM AUTHOR]

As data analytics has become an important application for modern data management systems, a new category of data management system has appeared recently: the scalable linear algebra system. We argue that a parallel or distributed database system is actually an excellent platform upon which to build such functionality. Most relational systems already have support for cost-based optimization--which is vital to scaling linear algebra computations--and it is well known how to make relational systems scalable. We show that by making just a few changes to a parallel/distributed relational database system, such a system can become a competitive platform for scalable linear algebra. Taken together, our results should at least raise the possibility that brand new systems designed from the ground up to support scalable linear algebra are not absolutely necessary, and that such systems could instead be built on top of existing relational technology. [ABSTRACT FROM AUTHOR]

The article discusses compiler and code generation concepts and utilizes examples from C and C++ computer languages. It also discusses various transformation or optimization functions that compilers can perform.

The article discusses the implications of Amdahl's law for tail latency and its consequences for parallel processing and single-thread performance optimization for data-center hardware development and software architecture design. The alleged importance of balancing memory resource usage and computational resources is described along with the implications of queuing theory for hardware design.

Improving performance is a central concern for software developers. To locate optimization opportunities, developers rely on software profilers. However, these profilers only report where programs spend their time: optimizing that code may have no impact on performance. Past profilers thus both waste developer time and make it difficult for them to uncover significant optimization opportunities. This paper introduces causal profiling. Unlike past profiling approaches, causal profiling indicates exactly where programmers should focus their optimization efforts, and quantifies their potential impact. Causal profiling works by running performance experiments during program execution. Each experiment calculates the impact of any potential optimization by virtually speeding up code: inserting pauses that slow down all other code running concurrently. The key insight is that this slowdown has the same relative effect as running that line faster, thus "virtually" speeding it up. We present Coz, a causal profiler, which we evaluate on a range of highly-tuned applications such as Memcached, SQLite, and the PARSEC benchmark suite. Coz identifies previously unknown optimization opportunities that are both significant and targeted. Guided by Coz, we improve the performance of Memcached by 9%, SQLite by 25%, and accelerate six PARSEC applications by as much as 68%; in most cases, these optimizations involve modifying under 10 lines of code. [ABSTRACT FROM AUTHOR]

What is a fair way to assign rooms to several housemates, and divide the rent between them? This is not just a theoretical question: many people have used the Spliddit website to obtain envy-free solutions to rent division instances. But envy freeness, in and of itself, is insufficient to guarantee outcomes that people view as intuitive and acceptable. We therefore focus on solutions that optimize a criterion of social justice, subject to the envy freeness constraint, in order to pinpoint the "fairest" solutions. We develop a general algorithmic framework that enables the computation of such solutions in polynomial time. We then study the relations between natural optimization objectives, and identify the maximin solution, which maximizes the minimum utility subject to envy freeness, as the most attractive. We demonstrate, using experiments on real data from Spliddit, that the maximin solution gives rise to significant gains in terms of our optimization objectives. Finally, a user study with Spliddit users as subjects demonstrates that people find the maximin solution to be significantly fairer than arbitrary envy-free solutions; this user study is unprecedented in that it asks people about their real-world rent division instances. Based on these results, the maximin solution has been deployed on Spliddit since April 2015. [ABSTRACT FROM AUTHOR]

We propose a generalization of the classical database query optimization problem: multi-objective parametric query (MPQ) optimization. MPQ compares alternative processing plans according to multiple execution cost metrics. It also models missing pieces of information on which plan costs depend upon as parameters. Both features are crucial to model query processing on modern data processing platforms. MPQ generalizes previously proposed query optimization variants, such as multi-objective query optimization, parametric query optimization, and traditional query optimization. We show, however, that the MPQ problem has different properties than prior variants and solving it requires novel methods. We present an algorithm that solves the MPQ problem and finds, for a given query, the set of all relevant query plans. This set contains all plans that realize optimal execution cost tradeoffs for any combination of parameter values. Our algorithm is based on dynamic programming and recursively constructs relevant query plans by combining relevant plans for query parts. We assume that all plan execution cost functions are piecewise-linear in the parameters. We use linear programming to compare alternative plans and to identify plans that are not relevant. We present a complexity analysis of our algorithm and experimentally evaluate its performance. [ABSTRACT FROM AUTHOR]

The optimization of short sequences of loop-free, fixed-point assembly code sequences is an important problem in high-performance computing. However, the competing constraints of transformation correctness and performance improvement often force even special purpose compilers to produce sub-optimal code. We show that by encoding these constraints as terms in a cost function, and using a Markov Chain Monte Carlo sampler to rapidly explore the space of all possible code sequences, we are able to generate aggressively optimized versions of a given target code sequence. Beginning from binaries compiled by llvm −O0, we are able to produce provably correct code sequences that either match or outperform the code produced by gcc −O3, icc −O3, and in some cases expert handwritten assembly. [ABSTRACT FROM AUTHOR]

We introduce bisimulation up to congruence as a technique for proving language equivalence of nondeterministic finite automata. Exploiting this technique, we devise an optimization of the classic algorithm by Hopcroft and Karp. We compare our approach to the recently introduced antichain algorithms and we give concrete examples where we exponentially improve over antichains. Experimental results show significant improvements. [ABSTRACT FROM AUTHOR]

The article discusses the construction of web applications for mobile devices, focusing on best practices for website performance optimization as of August 2013. Recommendations include minimizing HTTP requests, using compression on content that is not an image or a video, preloading components, and managing caches. Topics include website design, software applications, the JavaScript computer program language, cascading style sheets (CSS), and the potential differences between desktop and mobile design.

The article discusses strategies for optimizing the performance of websites as of August 2013, focusing on front-end optimization that improves user experiences. Topics include loading times, the increasing use of mobile devices by consumers, and variances in mobile latency and download speeds. Recommendations include reducing HTTP requests, using browser caching, and embedding resources in the HTML document markup language. Network connections and the SPDY protocol for avoiding performance bottlenecks from the Internet services company Google Inc.

VLSI placement optimizes locations of circuit components so as to reduce interconnect. Formulated in terms of (hyper)graphs, it is NP-hard, and yet must be solved for challenging million-node instances within several hours. We propose an algorithm for large-scale placement that outperforms prior art both in run time and solution quality on standard benchmarks. The algorithm is more straightforward than existing placers and easier to integrate into timing-closure flows. Our C++ implementation is compact, self-contained and exploits instruction-level and thread-level parallelism.Due to its simplicity and superior performance, the algorithm has been adopted in the industry and was extended by several university groups to multi-objective optimization. [ABSTRACT FROM AUTHOR]

The article discusses OpenFlow technology for Internet Protocol (IP) networks that change traditional computer networks through software-based platforming. Topics include the bidirectional utilization of bandwidth for coordinated data transfer by internal application systems, tenantized networking that preserves virtual machine isolation, and the preservation of IP addresses across subnetworks in game servers. Routing algorithms, smart phone software applications, and global network optimization are mentioned.

Avoid premature commitment, seek design alternatives, and automatically generate performance-optimized software. [ABSTRACT FROM AUTHOR]

The article presents calendar of events of computer science meetings to be held in the year 2000 that are sponsored by ACM published in the January 2000 issue of the journal Communications of the ACM. Some of the meetings include: "Workshop on the Practical Aspects on Declarative Languages," to be held on January 17 and 18, 2000 in Boston, Massachusetts; "Open Forum on Metadata Registries," to be held from January 17 to 21, 2000 in Santa Fe, New Mexico; "4th Java in the Computing Curriculum Conference," to be held on January 24, 2000 in London, England; "7th Dimacs Implementation Challenge: Semidefinite and Related Optimization Problems," to held from January 24 to 26, 2000 in Piscataway, New Jersey; "20th Annual Conference of the Texas Computer Education Association," to be held between February 8 and 11, 2000 in Austin, Texas; "7th International Conference on Intelligence in Services and Networks Telecommunications and IT Convergence Enabling Service E-volution," to be held from February 23 to 25, 2000 in Athens, Greece.

A fundamental analysis step in an advanced optimizing compiler (as well as many other software tools) is data dependence analysis for arrays. This means deciding if two references to an array can refer to the same element and if so, under what conditions. This information is used to determine allowable program transformations and optimizations. For example, we can determine that in the following code fragment, no location of the array is both read and written. Once we also verify that no location is written more than once, we know that the writes can be done in any order. [ABSTRACT FROM AUTHOR]

Automated program transformation systems are emerging as the basis fur a new programming methodology in which high-level, understandable specifications we transformed into efficient programs. Subsequent modification of the original specification will be dealt with by reimplementation of the specification. For such a system to be practical these reintplementations must occur relatively quickly and reliably in comparison with the original implementation. We believe that reimplementation requires that a formal document-the program development-be constructs during the development process explaining the resulting implementation to future maintainers of the specification. The overall goal of our work is to develop a language for capturing and explaining these developments and the resulting implementations. This language must be capable of expressing:1) the implementor's goal structure; 2) all program manipulations necessary for implementation; and 3) optimization and plans of such optimizations. We discuss the documentation requirements of the development process and then describe a prototype system jot constructing and maintaining this documentation information. Finally we indicate many remaining, open issues and the directions to be taken in the pursuit of adequate solutions. [ABSTRACT FROM AUTHOR]

A new technique of program transformation, called "recursion introduction," is described and applied to two algorithms which solve pattern matching problems. By using recursion introduction, algorithms which manipulate a stack are first translated into recursive algorithms in which no stack operations occur. These algorithms are then subjected to a second transformation, a method of recursion elimination called "tabulation," to produce programs with a very efficient running time. In particular, it is shown how the fast linear pattern matching algorithm of Knuth, Morris, and Pratt can be derived in a few steps from a simple nonlinear stack algorithm. [ABSTRACT FROM AUTHOR]

In certain data base organization schemes the cost per access may increase due to structural inefficiencies caused by updates. By reorganizing the data base the cost per access may be reduced. However, the high cost of a reorganization prohibits frequent reorganizations. This paper examines strategies for selecting the optimum reorganization points. [ABSTRACT FROM AUTHOR]

Great strides are being made in finding fast alternatives to the slow disks that dominate storage systems, but fast media are not nearly enough. INSET: Overhauling Systems Operations. [ABSTRACT FROM AUTHOR]

The article presents a response to a question on computer code optimization and readability.

The article discusses the computer data management concept of query optimization, and introduces an article in the journal on the subject of parametric and multi-objective query optimization.

The article presents two posts from computer technology bloggers John Langford and Ruben Ortega on the topics of algorithms in systems processing, collaboration, and self-organizing teams. According to Ortega, self-organizing teams balance responsibility and freedom as participants typically assume champion, mentor, promoter, and terminator roles. Langford describes learning through exploration and the optimization of non-linear algorithms that can index effectively through the interpretation of data.

An introduction is presented to the article "Stochastic Program Optimization" by Eric Schkufza, Rahul Sharma, and Alex Aiken, which discusses the use of stochastic techniques in program synthesis.

This article refers to another article that was published in the October 1970 issue of the "Journal of the ACM," which discussed the generation of optimal code. A restriction was imposed on the commands allowing register-register operation. However, allowing the result of a register-register operation to be placed into any register makes their results irrelevant, since such generality is not available in most present day machines. Instead, most present day machines place the result in the register containing the first operand. A new algorithm produces code in the same manner as the old one, with the same number of registers available at each node of the tree. The novelty of this algorithm is that it uses indirect register specification. As a result, the registers can be ordered to fit the instruction set of present day machines. The old algorithm was accompanied by proofs of its correctness and optimality. These proofs are still valid for the improved algorithm since the new algorithm does not violate any of the hypotheses of those proofs.

For computer systems in which it is practical to determine the instantaneous drum position, a popular discipline for determining the sequence in which the records are to be accessed is the so-called shortest- latency-time-first, SLTF, discipline. When a collection of varying-length records is to be accessed from specified drum positions, it is known that the SLTF discipline does not necessarily minimize the drum latency time. However, we show that the total time to access the entire collection for any SLTF schedule is never as much as a drum revolution longer than a minimum latency schedule. [ABSTRACT FROM AUTHOR]

The author discusses the concept of a knee in terms of computer program performance, defined as a section of a curve where response times and throughput are optimally balanced. An argument by computer scientist Neil Gunther that such knees are not based on mathematical discontinuities, but merely reflect human preferences, is critiqued.

The article discusses an article published in the journal which discusses computer patches that use evolutionary computation to find and repair computer bugs. The author discusses how search-based optimization can allow software programmers to locate computer bugs using optimization algorithms, a process known as search based software engineering (SBSE).

The article discusses the algorithm of eigenvalues of a symmetric, real, tridiagonal matrix. The algorithm utilizes a rational variant of the QR transformation with the explicit shift for the computation of all the eigenvalues of a symmetric and real tridiagonal matrix. Detailed description of procedures to be used to reduce any symmetric matrix to tridiagonal form is provided. The procedure provides for the end-for-end turning of the matrix to bring large entries to the computation.