Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userGeneric Connectivity-Based CGRA Mapping via Integer Linear Programming
147
0
0.0
(
0
)
Added by
Matthew Walker
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Coarse-grained reconfigurable architectures (CGRAs) are programmable logic devices with large coarse-grained ALU-like logic blocks, and multi-bit datapath-style routing. CGRAs often have relatively restricted data routing networks, so they attract CAD mapping tools that use exact methods, such as Integer Linear Programming (ILP). However, tools that target general architectures must use large constraint systems to fully describe an architectures flexibility, resulting in lengthy run-times. In this paper, we propose to derive connectivity information from an otherwise generic device model, and use this to create simpler ILPs, which we combine in an iterative schedule and retain most of the exactness of a fully-generic ILP approach. This new approach has a speed-up geometric mean of 5.88x when considering benchmarks that do not hit a time-limit of 7.5 hours on the fully-generic ILP, and 37.6x otherwise. This was measured using the set of benchmarks used to originally evaluate the fully-generic approach and several more benchmarks representing computation tasks, over three different CGRA architectures. All run-times of the new approach are less than 20 minutes, with 90th percentile time of 410 seconds. The proposed mapping techniques are integrated into, and evaluated using the open-source CGRA-ME architecture modelling and exploration framework.
rate research
Read More
Massive connectivity is a critical challenge of Internet of Things (IoT) networks. In this paper, we consider the grant-free uplink transmission of an IoT network with a multi-antenna base station (BS) and a large number of single-antenna IoT devices. Due to the sporadic nature of IoT devices, we formulate the joint activity detection and channel estimation (JADCE) problem as a group-sparse matrix estimation problem. Although many algorithms have been proposed to solve the JADCE problem, most of them are developed based on compressive sensing technique, yielding suboptimal solutions. In this paper, we first develop an efficient weighted $l_1$-norm minimization algorithm to better approximate the group sparsity than the existing mixed $l_1/l_2$-norm minimization. Although an enhanced estimation performance in terms of the mean squared error (MSE) can be achieved, the weighted $l_1$-norm minimization algorithm is still a convex relaxation of the original group-sparse matrix estimation problem, yielding a suboptimal solution. To this end, we further reformulate the JADCE problem as a mixed integer programming (MIP) problem, which can be solved by using the branch-and-bound method. As a result, we are able to obtain an optimal solution of the JADCE problem, which can be adopted as an upper bound to evaluate the effectiveness of the existing algorithms. Moreover, we also derive the minimum pilot sequence length required to fully recover the estimated matrix in the noiseless scenario. Simulation results show the performance gains of the proposed optimal algorithm over the proposed weighted $l_1$-norm algorithm and the conventional mixed $l_1/l_2$-norm algorithm. Results also show that the proposed algorithms require a short pilot sequence than the conventional algorithm to achieve the same estimation performance.
Recent advancements in procedural content generation via machine learning enable the generation of video-game levels that are aesthetically similar to human-authored examples. However, the generated levels are often unplayable without additional editing. We propose a generate-then-repair framework for automatic generation of playable levels adhering to specific styles. The framework constructs levels using a generative adversarial network (GAN) trained with human-authored examples and repairs them using a mixed-integer linear program (MIP) with playability constraints. A key component of the framework is computing minimum cost edits between the GAN generated level and the solution of the MIP solver, which we cast as a minimum cost network flow problem. Results show that the proposed framework generates a diverse range of playable levels, that capture the spatial relationships between objects exhibited in the human-authored levels.
Recently a novel framework has been proposed for designing the molecular structure of chemical compounds using both artificial neural networks (ANNs) and mixed integer linear programming (MILP). In the framework, we first define a feature vector $f(C)$ of a chemical graph $C$ and construct an ANN that maps $x=f(C)$ to a predicted value $eta(x)$ of a chemical property $pi$ to $C$. After this, we formulate an MILP that simulates the computation process of $f(C)$ from $C$ and that of $eta(x)$ from $x$. Given a target value $y^*$ of the chemical property $pi$, we infer a chemical graph $C^dagger$ such that $eta(f(C^dagger))=y^*$ by solving the MILP. In this paper, we use linear regression to construct a prediction function $eta$ instead of ANNs. For this, we derive an MILP formulation that simulates the computation process of a prediction function by linear regression. The results of computational experiments suggest our method can infer chemical graphs with around up to 50 non-hydrogen atoms.
In this paper, a mixed-integer linear programming formulation for the problem of obtaining task-relevant, multi-resolution, graph abstractions for resource-constrained agents is presented. The formulation leverages concepts from information-theoretic signal compression, specifically the information bottleneck (IB) method, to pose a graph abstraction problem as an optimal encoder search over the space of multi-resolution trees. The abstractions emerge in a task-relevant manner as a function of agent information-processing constraints, and are not provided to the system a priori. We detail our formulation and show how the problem can be realized as an integer linear program. A non-trivial numerical example is presented to demonstrate the utility in employing our approach to obtain hierarchical tree abstractions for resource-limited agents.
A novel framework has recently been proposed for designing the molecular structure of chemical compounds with a desired chemical property using both artificial neural networks and mixed integer linear programming. In this paper, we design a new method for inferring a polymer based on the framework. For this, we introduce a new way of representing a polymer as a form of monomer and define new descriptors that feature the structure of polymers. We also use linear regression as a building block of constructing a prediction function in the framework. The results of our computational experiments reveal a set of chemical properties on polymers to which a prediction function constructed with linear regression performs well. We also observe that the proposed method can infer polymers with up to 50 non-hydrogen atoms in a monomer form.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
