This paper explores automated robotic construction of clocháin2, a type of corbelled rock shelter, traditionally crafted by skilled workers. While robots have been employed for simple dry-stacking tasks in the past, such as construction of stone walls or vertical stone towers, the question of whether robots possess the capacity to construct more functional structures remains unanswered. This study presents a significant step forward in robotic dry-stacking of functional structures: the assembly of natural stones into freestanding clocháin structures. We also present a set of stackability measures to aid stone selection, which significantly improves the stability of the planned structures. Our sequential filtering approach, originally designed for planning stone walls, plays a foundational role in achieving stable clochán construction. Experimental results validate the effectiveness of the stackability measures and demonstrate the physical execution of dry-stacking clocháin, The progress demonstrated in this paper opens the door to robotic construction of a wide range of utility structures in unstructured environments.

We introduce a fast approximate stability analysis into an automated dry stacking procedure. Evaluating structural stability is essential for any type of construction, but especially challenging in techniques where building elements remain distinct and do not use fasteners or adhesives. Due to the irregular shape of construction materials, autonomous agents have restricted knowledge of contact geometry, which makes existing analysis tools difficult to deploy. In this paper, a geometric safety factor called kern is used to estimate how much the contact interface can shrink and the structure still be feasible, where feasibility can be checked efficiently using linear programming. We validate the stability measure by comparing the proposed methods with a fully simulated shaking test in 2D. We also improve existing heuristics-based planning by adding the proposed measure into the assembly process.

In on-demand ridesharing, optimizing the quality of supply-demand matches and minimizing the number of unfulfilled trip requests is an important business problem. One approach is to match supply with demand based on greedy local heuristics, which is sub-optimal at the market level. Another approach is to find the globally optimal matching over the whole marketplace. However, because the computation has high latency, and usually requires aggregate supply and demand data over time, instead of only the supply and demand at the time of individual trip requests, it is unfeasible to perform the global optimization for every trip request in realtime. This paper proposes a solution that performs a global optimization offline periodically based on forecasted supply and demand data, and uses the offline results to guide realtime supply and demand matching. The solution is a novel two-stage robust optimization scheme for supply-demand matching in on-demand ridesharing. We implemented the proposed solution and evaluated it using simulated trips based on public industry data. It reduces the number of unfulfilled trips significantly compared to a state-of-the-art approach.

We describe a method for automatically building structures from stacked, irregularly shaped objects. This is a simplified model for the problem of building dry stacked structures (i.e. no mortar) from found stones. Although automating such construction methods would be ideally suited for disaster areas or remote environments, currently such structures need to be built by skilled masons. No practical methods for automating the assembly planning process are known. The problem is challenging since each assembly action can be drawn from a continuous space poses for an object and several local geometric and physical considerations strongly affect the overall stability. We show that structures that are built following a stacking order for perfect bricks can accommodate a limited amount of irregularity, however, their performance degrades quickly when objects deviate from their ideal shape. We present a strategy for stacking irregular shapes that first considers geometric and physical constraints to find a small set of feasible actions and then further refines this set by using heuristics gathered from instructional literature for masons. The proposed method of choosing assembly actions allows construction with objects that contain a significant amount of variation.

We propose a reinforcement learning approach for automatically building dry stacked (i.e. no mortar) structures with irregular objects. Stacking irregular objects is a challenging problem since each assembly action can be drawn from a continuous space of poses for an object, and several local geometric and physical considerations strongly affect the stability. To tackle this challenge, we concentrate on a simplified 2D version of the problem. We present a reinforcement learning algorithm based on deep Q-learning, where the learned Q-function, which maps state-action pairs into expected long-term rewards, is represented by a deep neural network. As the action space is continuous the Q-network is trained by sampling a finite number of actions that consider both geometric and physical constraints to approximate the target Q-values, Experiments show that the proposed method outperforms previous heuristics-based planning, leading to super construction with objects containing a significant amount of variations. We validate the generated stacking plans by executing them using a robot arm and manufactured, irregular objects.

This paper presents a novel single-image super-resolution (SR) procedure, which upscales a given low-resolution (LR) input image to a high-resolution image while preserving the textural and structural information. First, we construct a new type of bivariate rational fractal interpolation model and investigate its analytical properties. This model has different forms of expression with various values of the scaling factors and shape parameters; thus, it can be employed to better describe image features than current interpolation schemes. Furthermore, this model combines the advantages of rational interpolation and fractal interpolation, and its effectiveness is validated through theoretical analysis. Second, we develop a single-image SR algorithm based on the proposed model. The LR input image is divided into texture and non-texture regions, and then, the image is interpolated according to the characteristics of the local structure. Specifically, in the texture region, the scaling factor calculation is the critical step. We present a method to accurately calculate scaling factors based on local fractal analysis. Extensive experiments and comparisons with the other state-of-the-art methods show that our algorithm achieves competitive performance, with finer details and sharper edges.

Service resiliency is crucial to the operation of global-scale cloud applications with fine-grained replication (FGR). If poorly designed, a few disruptions may cause cascading failures or severely impair the level of service. Due to high complexity of FGR configuration problem, existing techniques usually rely on over-provisioning and static replica configuration to achieve reliability to a certain extent. Such approaches may suffer from slow disruption response and unnecessary sacrifice on service availability. This paper proposes a novel problem formulation of online FGR configuration for service resiliency, which includes a new definition of service availability and a new constraint of zero-data-move configuration. To efficiently solve the proposed problem, this paper presents a brand new optimal dimension reduction technique - Replica Vector Decomposition (RVD), which greatly reduces problem complexity while preserving solution optimality (by formal proof). A RVD-based framework is designed for the online FGR configuration problem. Our evaluation results show that RVD-based FGR configuration scheme achieves substantial speedup of online disruption response, significantly improves service resiliency, and maintains a high level of service in the face of multiple disruptions.

This article presents our research towards developing novel and fundamental methodologies for data representation using spike-timing-dependent encoding. Time encoding efficiently maps a signal's amplitude information into a spike time sequence that represents the input data and offers perfect recovery for band-limited stimuli. In this article, we pattern the neural activities across multiple timescales and encode the sensory information using time-dependent temporal scales. The spike encoding methodologies for autonomous classification of time-series signatures are explored using near-chaotic reservoir computing. The proposed spiking neuron is compact, low power, and robust. A hardware implementation of these results is expected to produce an agile hardware implementation of time encoding as a signal conditioner for dynamical neural processor designs.

The earlier warning of electronic systems failure provided by canaries attached to them can effectively reduce system life cycle operational costs with respect to spare parts and replacement decisions. This paper presents a theoretical model for the derivation of the expected total cost per unit time in terms of the order interval and maximum allowable stock level.

Technology mapping and placement have a significant impact on delays in standard cell-based very large scale integrated circuits. Traditionally, these steps are applied separately to optimize the delays, possibly since efficient algorithms that allow the simultaneous exploration of the mapping and placement solution spaces are unknown. In this paper, we present an exact polynomial time algorithm for delay-optimal placement of a tree and extend the same to simultaneous technology mapping and placement for the optimal delay in the tree. We extend the algorithm by employing Lagrangian relaxation technique, which assesses the timing criticality of paths beyond a tree, to optimize the delays in directed acyclic graphs. Experimental results on benchmark circuits in a 70 nm technology show that our algorithms improve timing significantly with remarkably less runtimes compared to a competitive approach of iterative conventional timing-driven mapping and multilevel placement.

The progress of GPU (Graphics Processing Unit) technology opens a new avenue for boosting computing power. This work is an attempt to exploit the GPU for accelerating VLSI circuit optimization. We propose GPU-based parallel computing techniques and apply them on simultaneous gate sizing and threshold voltage assignment, which is a popular method for VLSI performance and power optimization. These techniques include efficient task scheduling and memory organization, all of which are aimed to fully utilize the advantages of GPUs. Compared to conventional sequential computation, our techniques can provide up to 56× (39× on average) speedup without any sacrifice on solution quality.

Transistor sizing is a classic Computer-Aided Design problem that has received much attention in the literature. Due to the increasing importance of process variations in deep sub-micron circuits, nominal circuit tuning is not sufficient, and the sizing problem warrants revisiting. This paper addresses the sizing problem statistically in which transistor sizes are automatically adjusted to maximize parametric yield at a given timing performance, or maximize performance at a required parametric yield. Specifically, we describe an implementation of a statistical tuner using interior point nonlinear optimization with an objective function that is directly dependent on statistical process variation. Our results show that for process variation sensitive circuits, consisting of thousands of independently tunable devices, a statistically aware tuner can give more robust, higher yield solutions when compared to deterministic circuit tuning and is thus an attractive alternative to the Monte Carlo methods that are typically used to size devices in such circuits. To the best of our knowledge, this is the first publication of a working system to optimize device sizes in custom circuits using a process variation aware tuner.

Networks-on-chip (NoC) is emerging as a promising communication structure, which is scalable with respect to chip complexity. Meanwhile, latest chip designs are increasingly leveraging multiple voltage-frequency domains for energy-efficiency improvement. In this work, we propose a simultaneous task and voltage scheduling algorithm for energy minimization in NoC based designs. The energy-latency tradeoff is handled by Lagrangian relaxation. The core algorithm is a clustering based approach which not only assigns voltage levels and starting time to each task (or Processing Element) but also naturally finds voltage-frequency clusters. Compared to a recent previous work, which performs task scheduling and voltage assignment sequentially, our method leads to an average of 20% energy reduction.

Clock mesh is widely used in microprocessor designs for achieving low clock skew and high variation tolerance. Clock mesh optimization is a very difficult problem because it has highly-connected structure and requires accurate delay models which are computationally expensive. Existing methods on clock network optimization are either restricted to clock trees, which are easy to be separated into smaller problems, or naive heuristics based on crude delay models. In this paper, we propose a clock mesh sizing algorithm which is aimed to minimize mesh wire area with consideration of clock skew constraints. This algorithm is a systematic solution search through rigorous Sequential Quadratic Programming (SQP). The SQP is guided by an efficient adjoint sensitivity analysis which has near-SPICE-level accuracy and faster-than-SPICE speed. Experimental results on various benchmark circuits indicate that our algorithm leads to significant wire area reduction while maintaining low clock skew.

Gate sizing and threshold voltage (Vt) assignment are popular techniques for circuit timing and power optimization. Existing methods, by and large, are either sensitivity-driven heuristics or based on discretizing continuous optimization solutions. Sensitivity-driven heuristics are easily trapped in local optima and the discretization may be subject to remarkable errors. In this paper, we propose a systematic combinatorial approach for simultaneous gate sizing and Vtassignment. The core idea of this approach is joint relaxation and restriction, which employs consistency relaxation and coupled bi-directional solution search. The process of joint relaxation and restriction is conducted iteratively to systematically improve solutions. Our algorithm is compared with a state-of-the-art previous work on benchmark circuits. The results from our algorithm can lead to about 22% less power dissipation subject to the same timing constraints.

The progress of GPU (Graphics Processing Unit) technology opens a new avenue for boosting computing power. This work is an attempt to exploit GPU for accelerating VLSI circuit optimization. We propose GPU-based parallel computing techniques and apply them on simultaneous gate sizing and threshold voltage assignment, which is often employed in practice for performance and power optimization. These techniques are aimed to fully utilize the benefits of GPU through efficient task scheduling and memory organization. Compared to conventional sequential computation, our techniques can provide up to 56x speedup without any sacrifice on solution quality.

Gate sizing and threshold voltage (Vt) assignment are popular tech-niques for circuit timing and power optimization. Existing meth-ods, by and large, are either sensitivity-driven heuristics or based on rounding continuous optimization solutions. Sensitivity-driven heuristics are easily trapped in local optimum and the rounding is subject to remarkable errors. In this paper, we propose a system-atic combinatorial approach for simultaneous gate sizing and Vt assignment. The core ideas of this approach include consistency relaxation and coupled bi-directional search. Our algorithm is com-pared with a state-of-the-art previous work on benchmark circuits. The results from our algorithm can lead to about 24 % less power dissipation subject to the same timing constraints.

Technology mapping and placement have significant impact on the delays in standard cell based very large scale integrated (VLSI) circuits. Traditionally, these steps are applied separately to optimize delays, possibly since efficient algorithms that allow the simultaneous exploration of the mapping and placement solution spaces are unknown. In this paper, we present an exact polynomial time algorithm for delay-optimal placement of a tree and extend the same to simultaneous technology mapping and placement for optimal delay in the tree. We extend the algorithm by employing Lagrangian relaxation technique, which assesses the timing criticality of paths beyond a tree, to optimize the delays in directed acyclic graphs (DAGs). Experimental results on benchmark circuits in a 70 nm technology show that our algorithms improve timing significantly with remarkably less run-times compared to a competitive approach of iterative conventional timing driven mapping and multi-level placement.

Recently, microprocessor industry is headed in the direction of multi-core designs in order to continue the chip performance growth. We investigate buffer insertion, which is a critical timing optimization technique, in the context of an industrial multi-core processor design methodology. Different from the conventional formulation, buffer insertion in this case requires a single solution to accommodate different scenarios. If the conventional buffer insertion is performed for each scenario separately, there may be different solutions corresponding to these scenarios. A naive approach is to select one scenario's solution that is most critical among all scenarios and apply it to all the scenarios. However, a good solution for one scenario maybe a poor one for another scenario. We propose algorithmic techniques for solving these multi-scenario buffer insertion problems. Compared to the naive approach, our algorithm can improve slack by 102ps on average for maxslack solutions. For min-cost solutions, our algorithm causes no timing violation while the naive approach results in 35% timing violations. Moreover, the computation speed of our algorithm is faster

Recently, the microprocessor industry is headed in the direction of multicore designs in order to continue the chip performance growth. We investigate buffer insertion, which is a critical timing optimization technique, in the context of an industrial multicore processor design methodology. Different from the conventional formulation, buffer insertion in this case requires a single solution to accommodate different scenarios, since each core has its own parameters. If conventional buffer insertion is performed for each scenario separately, there may be a different solution corresponding to each of these scenarios. A straightforward approach is to judiciously select a solution from one scenario and apply it to all the scenarios. However, a good solution for one scenario may be a poor one for another. We propose several algorithmic techniques for solving these multiscenario buffer insertion problems. Compared with a straightforward extension of the conventional buffer insertion, our algorithm can improve slack by 20-280 ps for max-slack solutions. For min-cost solutions, our algorithm causes no timing violation, while the extended conventional buffering results in 35% timing violations. Moreover, the computation speed of our algorithm is faster.