algorithmic paradigms such as divide-and-conquer (D&C) are proposed to guide developers in designing efficient algorithms, but it can still be difficult to apply algorithmic paradigms to practical tasks. To ease t...
详细信息
algorithmic paradigms such as divide-and-conquer (D&C) are proposed to guide developers in designing efficient algorithms, but it can still be difficult to apply algorithmic paradigms to practical tasks. To ease the usage of paradigms, many research efforts have been devoted to the automatic application of algorithmic paradigms. However, most existing approaches to this problem rely on syntax-based program transformations and thus put significant restrictions on the original program. In this article, we study the automatic application of D&C and several similar paradigms, denoted as D&C-like algorithmic paradigms, and aim to remove the restrictions from syntax-based transformations. To achieve this goal, we propose an efficient synthesizer, named AutoLifter, which does not depend on syntax-based transformations. Specifically, the main challenge of applying algorithmic paradigms is from the large scale of the synthesized programs, and AutoLifter addresses this challenge by applying two novel decomposition methods that do not depend on the syntax of the input program, component elimination and variable elimination, to soundly divide the whole problem into simpler subtasks, each synthesizing a sub-program of the final program and being tractable with existing synthesizers. We evaluate AutoLifter on 96 programming tasks related to six different algorithmic paradigms. AutoLifter solves 82/96 tasks with an average time cost of 20.17 s, significantly outperforming existing approaches.
The locality of a graph problem is the smallest distance T such that each node can choose its own part of the solution based on its radius -T neighborhood. In many settings, a graph problem can be solved efficiently w...
详细信息
The locality of a graph problem is the smallest distance T such that each node can choose its own part of the solution based on its radius -T neighborhood. In many settings, a graph problem can be solved efficiently with a distributed or parallel algorithm if and only if it has a small locality. In this work we seek to automate the study of solvability and locality: given the description of a graph problem II, we would like to determine if II is solvable and what is the asymptotic locality of II as a function of the size of the graph. Put otherwise, we seek to automatically synthesize efficient distributed and parallel algorithms for solving II. We focus on locally checkable graph problems;these are problems in which a solution is globally feasible if it looks feasible in all constant-radius neighborhoods. Prior work on such problems has brought primarily bad news: questions related to locality are undecidable in general, and even if we focus on the case of labeled paths and cycles, determining locality is PSPACE-hard (Balliu et al., PODC 2019). We complement prior negative results with efficient algorithms for the cases of unlabeled paths and cycles and, as an extension, for rooted trees. We study locally checkable graph problems from an automata-theoretic perspective by representing a locally checkable problem II as a nondeterministic finite automaton M over a unary alphabet. We identify polynomial-time-computable properties of the automaton M that near-completely capture the solvability and locality of II in cycles and paths, with the exception of one specific case that is co-NP-complete.(c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://creativecommons .org /licenses /by /4 .0/).
We present a convex solution for the design of generalized accelerated gradient algorithms for strongly convex objective functions with Lipschitz continuous gradients. We utilize integral quadratic constraints and the...
详细信息
We present a convex solution for the design of generalized accelerated gradient algorithms for strongly convex objective functions with Lipschitz continuous gradients. We utilize integral quadratic constraints and the Youla parameterization from robust control theory to formulate a solution of the algorithm design problem as a convex semidefinite program. We establish explicit formulas for the optimal convergence rates and extend the proposed synthesis solution to extremum control problems.
We present the principles and the experiments of deduction based synthesis of merging algorithms for binary trees. Merging is an auxiliary function used in certain algorithms kir sorting of binary trees, however we al...
详细信息
ISBN:
(纸本)9781728195438
We present the principles and the experiments of deduction based synthesis of merging algorithms for binary trees. Merging is an auxiliary function used in certain algorithms kir sorting of binary trees, however we also address concatenation or unsorted trees (the result will also be in general not sorted) as well as merging of sorted trees (both inputs as well as the output are soiled). We follow the classical approach to deductive synthesis: the algorithm is extracted from the pro,11 of a synthesis conjecture, which asserts that the merged object exists. The novelty of our approach consists in using multisets lor expressing the fact that two trees have the same content, which also allows us to develop new powerful proof techniques. mostly by using induction based on the Noetherian ordering among trees induced by the strict inclusion of the corresponding multisets. As the synthesis proofs proceed on different alternatives, several versions or the algorithms are produced. The experiments result in 24 concatenation algorithms, 4 merging algorithms, as well as some sub-auxiliary algorithms for insertion of an element into the tree and for splitting a tree into two sub-trees having the elements smaller, respectively bigger, than a certain value.
There are increasing opportunities to calculate with distributed/parallel computing: many-core CPU, GPU, and FPGA. It is, however, generally difficult to come up with an algorithm suitable for distributed/parallel com...
详细信息
ISBN:
(纸本)9781728103921
There are increasing opportunities to calculate with distributed/parallel computing: many-core CPU, GPU, and FPGA. It is, however, generally difficult to come up with an algorithm suitable for distributed/parallel computing. There have been many researches on the automatic partitioning of programs and designs, but they have not performed reconstruction of the data flow in the algorithm level. In this paper, we apply partial synthesis method and synthesize algorithms for distributed/parallel environment automatically. We propose the template-based computing that aims to prevent the communications among the cores and chips to become overhead. With that template, an algorithm is synthesized by using conventional partial synthesis method, which performs synthesis iteratively modifying the template. The synthesis-problem generally becomes infeasible as its size becomes larger. Therefore, we propose the method to reduce the search space by adding constraints. The synthesis is performed for small instances of the target problem at first, and then the additional constraints are considered based on the synthesized algorithm. In the experiment, we synthesized algorithms for matrix vector multiplication with one-way ring -connected nodes to matrix of 32X32.
We demonstrate the possibility of automated synthesis of the Bubble-Sort algorithm as a rewrite program, a functional program, and an iterative program, starting from the specification. First a rewrite set of clauses ...
详细信息
ISBN:
(纸本)9781728131498
We demonstrate the possibility of automated synthesis of the Bubble-Sort algorithm as a rewrite program, a functional program, and an iterative program, starting from the specification. First a rewrite set of clauses for the algorithm Max-Sort is generated from the automatic proof of the synthesis conjecture, representing the main algorithm as well as the necessary auxiliary functions. This is then transformed into a tail recursive Bubble-Sort and by logical analysis the possibility of adding a flag for avoiding unnecessary recursions is identified. This new, more efficient algorithm is then transformed into a functional program, and finally into an imperative program. The practical experiments are performed using the Theorema system.
We demonstrate the deductive synthesis of the Min-Max-Sort algorithm using multisets in the frame of the Theorema system. Starting from the logical specification of the sorting function (input and output conditions), ...
详细信息
ISBN:
(数字)9781728173771
ISBN:
(纸本)9781728173764
We demonstrate the deductive synthesis of the Min-Max-Sort algorithm using multisets in the frame of the Theorema system. Starting from the logical specification of the sorting function (input and output conditions), we show how to construct a synthesis conjecture, from whose proof the algorithm can be constructed. For the proof we choose those inference methods and induction principles such that the synthesized algorithm consists of selecting at each step the minimum and the maximum of the list, and moving them at the ends of the list. We also show how to add, on a logical basis, a specific flag in order to stop the recursion as soon as the list is already sorted. During the main proof new conjectures are produced for the synthesis of auxiliary algorithms, and this process repeats in a cascading fashion until all necessary algorithms are produced. Our proof techniques, which are in natural style, include a novel approach using multisets and the use of cover sets for realizing Noetherian induction. The later has the advantage that the concrete induction hypotheses are created dynamically during the proof of the corresponding induction conclusion, thus no concrete induction principle or algorithm scheme is needed in advance. The synthesis mechanism is implemented in the frame of the Theorema system which allows the construction of mathematical theories, proving in natural style, and computing with the synthesized algorithms.
We develop logic and combinatorial methods for automating the generation of sorting algorithms for binary trees, starting from input-output specifications and producing conditional rewrite rules. The main approach con...
详细信息
We develop logic and combinatorial methods for automating the generation of sorting algorithms for binary trees, starting from input-output specifications and producing conditional rewrite rules. The main approach consists in proving (constructively) the existence of an appropriate output from every input. The proof may fail if some necessary sub-algorithms are lacking. Then, their specifications are suggested and their synthesis is performed by the same principles. Our main goal is to avoid the possibly prohibitive cost of pure resolution proofs by using a natural-style proving in which domain specific strategies and inference steps lead to a significant increase of efficiency. In addition to classical techniques for natural-style proving, we introduce novel ones (priority of certain types of assumptions, transformation of elementary goals into conditions, special criteria for decomposition of the goal and of the assumptions), as well as methods based on the properties of domain specific relations and functions. In particular, we use combinatorial techniques in order to generate possible witnesses, which in certain cases lead to the discovery of new induction principles. From the proof, the algorithm is extracted by transforming inductive proof steps into recursions, and case-based proof steps into conditionals. The approach is demonstrated in parallel using the Theorema system, by developing the theory, implementing the prover, and performing the proofs of the necessary properties and synthesis conjectures. It is also validated in the Coq system, which allows to compare the facilities of the two systems from the point of view of our application. (C) 2018 Elsevier Ltd. All rights reserved.
Mapping of large systems/computations on multiple chips/multiple cores needs sophisticated compilation methods. In this demonstration, we present our compiler tools for multi-chip and multi-core systems that considers...
详细信息
ISBN:
(纸本)9781728103976
Mapping of large systems/computations on multiple chips/multiple cores needs sophisticated compilation methods. In this demonstration, we present our compiler tools for multi-chip and multi-core systems that considers communication architecture and the related constraints for optimal mapping. Specifically, we demonstrate compilation methods for multi-chip connected with ring topology, and multi-core connected with mesh topology, assuming fine-grained reconfigurable cores, as well as generalization techniques for large problems size as convolutional neural networks. We will demonstrate our mappings methods starting from data-flow graphs (DFGs) and equations, specifically with applications to convolutional neural networks (CNNs) for convolution layers as well as fully connected layers.
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): ...
详细信息
ISBN:
(纸本)9781450349925
LCLs or locally checkable labelling problems (e.g. maximal independent set, maximal matching, and vertex colouring) in the LOCAL model of computation are very well-understood in cycles (toroidal 1-dimensional grids): every problem has a complexity of O(1), Theta(log* n), or Theta(n), and the design of optimal algorithms can be fully automated. This work develops the complexity theory of LCL problems for toroidal 2-dimensional grids. The complexity classes are the same as in the 1-dimensional case: O(1), Theta(log* n), and Theta(n). However, given an LCL problem it is undecidable whether its complexity is Theta(log* n) or Theta(n) in 2-dimensional grids. Nevertheless, if we correctly guess that the complexity of a problem is Theta(log* n), we can completely automate the design of optimal algorithms. For any problem we can find an algorithm that is of a normal formA' o S-k, whereA' is a finite function, Sk is an algorithm for finding a maximal independent set in kth power of the grid, and k is a constant. Finally, partially with the help of automated design tools, we classify the complexity of several concrete LCL problems related to colourings and orientations.
暂无评论