Cluster rightsizing facilitates cost-performance trade-off in resource-constrained clouds. Multidimensional bin-packing algorithms can address this rightsizing problem, but these assume that every task on the cluster is always active. In contrast, real-world tasks may be active only during specific time-periods, which allows reusing resources via time sharing and optimal packing. This motivates our generalized problem of rightsizing for time-limited tasks: given a timeline, time-periods and resource demands for tasks, the objective is to place the tasks on a minimum cost cluster of nodes without violating node capacities at any time instance. We design a baseline two-phase algorithm that performs penalty-based mapping of task to node-type and then, solves each node-type independently. We prove that the algorithm has an approximation ratio of O(D. min(m, T)), where D, m and$T$are the number of resources, node-types and timeslots, respectively, We then present an improved linear programming based mapping strategy, enhanced further with a cross-node-type filling mechanism. Our experiments on synthetic and real-world cluster traces show significant cost reduction by LP-based mapping compared to the baseline, and the filling mechanism improves further to produce solutions within 20% of (a lower-bound to) the optimal solution.

We present Move2Kube, a replatforming framework that automates the transformation of the deployment specification and development pipeline of an application from a non-Kubernetes platform to a Kubernetes-based one, minimizing changes to the application's functional implementation and architecture. Our contributions include: (1) a standardized intermediate representation to which diverse application deployment artifacts could be translated, (2) an extension framework for adding support for new source platforms, and target artifacts while allowing customization as per organizational standards. We provide initial evidence of its effectiveness in terms of effort reduction, and highlight the current research challenges and future lines of work. Move2Kube is being developed as an open source community project and it is available at https://move2kube.konveyor.io/

In this paper, we propose a novel approach for monolith decomposition, that maps the implementation structure of a monolith application to a functional structure that in turn can be mapped to business functionality. First, we infer the classes in the monolith application that are distinctively representative of the business functionality in the application domain. This is done using formal concept analysis on statically determined code flow structures in a completely automated manner. Then, we apply a clustering technique, guided by the inferred representatives, on the classes belonging to the monolith to group them into different types of partitions, mainly: 1) functional groups representing microservice candidates, 2) a utility class group, and 3) a group of classes that require significant refactoring to enable a clean microservice architecture. This results in microservice candidates that are naturally aligned with the different business functions exposed by the application. A detailed evaluation on four publicly available applications show that our approach is able to determine better quality microservice candidates when compared to other existing state of the art techniques. We also conclusively show that clustering quality metrics like modularity are not reliable indicators of microservice candidate goodness.

To enable statistical static timing analysis, for each cell in a digital library, a timing model that considers variations must be characterized. In this paper, we propose a dynamic method to accurately and efficiently characterize a cell's delay and output slew as a function of random mismatch variations. Based on a tight error bound for characterization using partial devices, our method sequentially performs simulations based on decreasing importance of devices and stops when the error requirement is met. Results on an industrial 32nm library demonstrate that the proposed method achieves significantly better accuracy-efficiency trade-off compared to other partial finite differencing approaches.

This paper presents a novel method, PTrace, to locally and uniformly trace convex bicriterial Pareto-optimal fronts for bicriterial optimization problems that, unlike existing methods, does not require derivatives of the objectives with respect to the design variables. The method computes a sequence of points along the front in a user-specified direction from a starting point, such that the points are roughly uniformly spaced as per a spacing constraint from the user. At each iteration, a local quadratic model of the front is used to estimate an appropriate weighted sum of objectives that, on optimization, will give the next point on the front. A single objective optimization on this weighted sum then generates the actual point, which is then used to build a new local model. The method uses convexity-based heuristics to improve on mildly sub-optimal results from the optimizer and reuses cached points to improve the optimization speed and quality. We test the method on a synthetic and a 6-T SRAM power-performance tradeoff test case to demonstrate its effectiveness.

The convex weighted-sum method for multi-objective optimization has the desirable property of not worsening the difficulty of the optimization problem, but can lead to very nonuniform sampling. This paper explains the relationship between the weights and the partial derivatives of the tradeoff surface, and shows how to use it to choose the right weights and uniformly sample largely convex tradeoff surfaces. It proposes a novel method, Derivative Pursuit (DP), that iteratively refines a simplicial approximation of the tradeoff surface by using partial derivative information to guide the weights generation. We demonstrate the improvements offered by DP on both synthetic and circuit test cases, including a 22 nm SRAM bitcell design problem with strict read and write yield constraints, and power and performance objectives.

At the nanoscale, no circuit parameters are truly deterministic; most quantities of practical interest present themselves as probability distributions. Thus, Monte Carlo techniques comprise the strategy of choice for statistical circuit analysis. There are many challenges in applying these techniques efficiently: circuit size, nonlinearity, simulation time, and required accuracy often conspire to make Monte Carlo analysis expensive and slow. Are we-the integrated circuit community-alone in facing such problems? As it turns out, the answer is “no.” Problems in computational finance share many of these characteristics: high dimensionality, profound nonlinearity, stringent accuracy requirements, and expensive sample evaluation. We perform a detailed experimental study of how one celebrated technique from that domain-quasi-Monte Carlo (QMC) simulation-can be adapted effectively for fast statistical circuit analysis. In contrast to traditional pseudorandom Monte Carlo sampling, QMC uses a (shorter) sequence of deterministically chosen sample points. We perform rigorous comparisons with both Monte Carlo and Latin hypercube sampling across a set of digital and analog circuits, in 90 and 45 nm technologies, varying in size from 30 to 400 devices. We consistently see superior performance from QMC, giving 2× to 8× speedup over conventional Monte Carlo for roughly 1% accuracy levels. We present rigorous theoretical arguments that support and explain this superior performance of QMC. The arguments also reveal insights regarding the (low) latent dimensionality of these circuit problems; for example, we observe that over half of the variance in our test circuits is from unidimensional behavior. This analysis provides quantitative support for recent enthusiasm in dimensionality reduction of circuit problems.

The data retention voltage (DRV) defines the minimum supply voltage for an SRAM cell to hold its state. Intra-die variation causes a statistical distribution of DRV for individual cells in a memory array. We present two fast and accurate methods to estimate the tail of the DRV distribution. The first method uses a new analytical model based on the relationship between DRV and static noise margin. The second method extends the statistical blockade technique to a recursive formulation. It uses conditional sampling for rapid statistical simulation and fits the results to a generalized Pareto distribution (GPD) model. Both the analytical DRV model and the generic GPD model show a good match with Monte Carlo simulation results and offer speedups of up to four or five orders of magnitude over Monte Carlo at the 6σ point. In addition, the two models show a very close agreement with each other at the tail up to 8σ. For error within 5% with a confidence of 95%, the analytical DRV model and the GPD model can predict DRV quantiles out to 8σ and 6.6σ respectively; and for the mean of the estimate, both models offer within 1% error relative to Monte Carlo at the 4σ point.

Static Random Access Memories (SRAMs) are key components of modern VLSI designs and a major bottleneck to technology scaling as they use the smallest size devices with high sensitivity to manufacturing details. Analysis performed at the "schematic" level can be deceiving as it ignores the interdependence between the implementation layout and the resulting electrical performance. We present a computational framework, referred to as "Virtual SRAM Fab", for analyzing and estimating pre-Si SRAM array manufacturing yield considering both lithographic and electrical variations. The framework is being demonstrated for SRAM design/optimization in 45nm nodes and currently being used for both 32nm and 22nm technology nodes. The application and merit of the framework are illustrated using two different SRAM cells in a 45nm PD/SOI technology, which have been designed for similar stability/performance, but exhibit different parametric yields due to layout/lithographic variations. We also demonstrate the application of Virtual SRAM Fab for prediction of layout-induced imbalance in an 8T cell, which is a popular candidate for SRAM implementation in 32-22nm technology nodes.

Circuit reliability under random parametric variation is an area of growing concern. For highly replicated circuits, e.g., static random access memories (SRAMs), a rare statistical event for one circuit may induce a not-so-rare system failure. Existing techniques perform poorly when tasked to generate both efficient sampling and sound statistics for these rare events. Statistical blockade is a novel Monte Carlo technique that allows us to efficiently filter-to block-unwanted samples that are insufficiently rare in the tail distributions we seek. The method synthesizes ideas from data mining and extreme value theory and, for the challenging application of SRAM yield analysis, shows speedups of 10 - 100 times over standard Monte Carlo.

Intra-die manufacturing variations are unavoidable in nanoscale processes. These variations often exhibit strong spatial correlation. Standard grid-based models assume model parameters (grid-size, regularity) in an ad hoc manner and can have high measurement cost. The random Leld model overcomes these issues. However, no general algorithm has been proposed for the practical use of this model in statistical CAD tools. In this paper, we propose a robust and efficient numerical method, based on the Galerkin technique and Karhunen Loeve Expansion, that enables effective use of the model. We test the effectiveness of the technique using a Monte Carlo-based Statistical Static Timing Analysis algorithm, and see errors less than 0.7%, while reducing the number of random variables from thousands to 25, resulting in speedups of up to 100 x.

Statistical static timing analysis (SSTA) has emerged as an essential tool for nanoscale designs. Monte Carlo methods are universally employed to validate the accuracy of the approximations made in all SSTA tools, but Monte Carlo itself is never employed as a strategy for practical SSTA. It is widely believed to be ldquotoo slowrdquo - despite an uncomfortable lack of rigorous studies to support this belief. We offer the first large-scale study to refute this belief. We synthesize recent results from fast quasi-Monte Carlo (QMC) deterministic sampling and efficient Karhunen-Loeve expansion (KLE) models of spatial correlation to show that Monte Carlo SSTA need not be slow. Indeed, we show for the ISCAS89 circuits, a few hundred, well-chosen sample points can achieve errors within 5%, with no assumptions on gate models, wire models, or the core STA engine, with runtimes less than 90 s.

Interval methods offer a general fine-grain strategy for modeling correlated range uncertainties in numerical algorithms. We present a new improved interval algebra that extends the classical affine form to a more rigorous statistical foundation. Range uncertainties now take the form of confidence intervals. In place of pessimistic interval bounds, we minimize the probability of numerical "escape"; this can tighten interval bounds by an order of magnitude while yielding 10-100 times speedups over Monte Carlo. The formulation relies on the following three critical ideas: liberating the affine model from the assumption of symmetric intervals; a unifying optimization formulation; and a concrete probabilistic model. We refer to these as probabilistic intervals for brevity. Our goal is to understand where we might use these as a surrogate for expensive explicit statistical computations. Results from sparse matrices and graph delay algorithms demonstrate the utility of the approach and the remaining challenges.

The number and magnitude of process variation sources are increasing as we scale further into the nano regime. Today's most successful response surface methods limit us to low-order forms -- linear, quadratic -- to make the fitting tractable. Unfortunately, not all variation-al scenarios are well modeled with low-order surfaces. We show how to exploit latent variable regression ideas to support efficient extraction of arbitrarily nonlinear statistical response surfaces. An implementation of these ideas called SiLVR, applied to a range of analog and digital circuits, in technologies from 90 to 45nm, shows significant improvements in prediction, with errors reduced by up to 21X, with very reasonable runtime costs.

Interval methods offer a general, fine-grain strategy for modeling correlated range uncertainties in numerical algorithms. We present a new, improved interval algebra that extends the classical affine form to a more rigorous statistical foundation. Range uncertainties now take the form of confidence intervals. In place of pessimistic interval bounds, we minimize the probability of numerical "escape"; this can tighten interval bounds by 10X, while yielding 10-100X speedups over Monte Carlo. The formulation relies on three critical ideas: liberating the affine model from the assumption of symmetric intervals; a unifying optimization formulation; and a concrete probabilistic model. We refer to these as probabilistic intervals, for brevity. Our goal is to understand where we might use these as a surrogate for expensive, explicit statistical computations. Results from sparse matrices and graph delay algorithms demonstrate the utility of the approach, and the remaining challenges.

The introduction of simulation-based analog synthesis tools creates a new challenge for analog modeling. These tools routinely visit 103 to 105 fully simulated circuit solution candidates. What might we do with all this circuit data? We show how to adapt recent ideas from large-scale data mining to build models that capture significant regions of this visited performance space, parameterized by variables manipulated by synthesis, trained by the data points visited during synthesis. Experimental results show that we can automatically build useful nonlinear regression models for large analog design spaces.