The capillary surface $u(x,y)$ near a cusp region satisfies the boundary value problem: \begin{eqnarray} \nabla \cdot \frac{\nabla u}{\sqrt{1+\left|\nabla u \right|^2}}&=&\kappa u \qquad \textrm{in }\left\{(x,y): 0<x,f_2(x)<y<f_1(x)\right\}\,, \label{0.1}\\ \nu \cdot \frac{\nabla u}{\sqrt{1+\left|\nabla u \right|^2}}&=& \cos \gamma_1 \qquad \textrm{on } y=f_1(x)\,,\\ \nu \cdot \frac{\nabla u}{\sqrt{1+\left|\nabla u \right|^2}}&=& \cos \gamma_2 \qquad \textrm{on } y=f_2(x)\,, \label{0.3} \end{eqnarray} where $\lim_{x\rightarrow 0}f_1(x),f_2(x)=0$, $\lim_{x\rightarrow 0}f'_1(x),f'_2(x)=0$. It is shown that the capillary surface is unbounded at the cusp and satisfies $u(x,y)=O\left(\frac{1}{f_1(x)-f_2(x)}\right)$, even for types of cusp not investigated previously (e.g. exponential cusps). By using a tangent cylinder coordinate system, we show that the exact solution $v(x,y)$ of the boundary value problem: \begin{eqnarray} \nabla \cdot \frac{\nabla v}{\left|\nabla v \right|}&=&\kappa v \qquad \textrm{in }\left\{(x,y): 0<x,f_2(x)<y<f_1(x)\right\}\,,\\ \nu \cdot \frac{\nabla v}{\left|\nabla v \right|}&=& \cos \gamma_1 \qquad \textrm{on } y=f_1(x)\,,\\ \nu \cdot \frac{\nabla v}{\left|\nabla v \right|}&=& \cos \gamma_2 \qquad \textrm{on } y=f_2(x)\,, \end{eqnarray} exhibits sixth order asymptotic accuracy to the capillary equations~\eqref{0.1}$-$\eqref{0.3} near a circular cusp. Finally, we show that the solution is bounded and can be defined to be continuous at a symmetric cusp ($f_1(x)=-f_2(x)$) with the supplementary contact angles ($\gamma_2=\pi-\gamma_1$). Also it is shown that the solution surface is of the order $O\left(f_1(x)\right)$, and moreover, the formal asymptotic series for a symmetric circular cusp region is derived.

The capillary surface $u(x,y)$ near a cusp region satisfies the boundary value problem: \begin{eqnarray} \nabla \cdot \frac{\nabla u}{\sqrt{1+\left|\nabla u \right|^2}}&=&\kappa u \qquad \textrm{in }\left\{(x,y): 0<x,f_2(x)<y<f_1(x)\right\}\,, \label{0.1}\\ \nu \cdot \frac{\nabla u}{\sqrt{1+\left|\nabla u \right|^2}}&=& \cos \gamma_1 \qquad \textrm{on } y=f_1(x)\,,\\ \nu \cdot \frac{\nabla u}{\sqrt{1+\left|\nabla u \right|^2}}&=& \cos \gamma_2 \qquad \textrm{on } y=f_2(x)\,, \label{0.3} \end{eqnarray} where $\lim_{x\rightarrow 0}f_1(x),f_2(x)=0$, $\lim_{x\rightarrow 0}f'_1(x),f'_2(x)=0$. It is shown that the capillary surface is unbounded at the cusp and satisfies $u(x,y)=O\left(\frac{1}{f_1(x)-f_2(x)}\right)$, even for types of cusp not investigated previously (e.g. exponential cusps). By using a tangent cylinder coordinate system, we show that the exact solution $v(x,y)$ of the boundary value problem: \begin{eqnarray} \nabla \cdot \frac{\nabla v}{\left|\nabla v \right|}&=&\kappa v \qquad \textrm{in }\left\{(x,y): 0<x,f_2(x)<y<f_1(x)\right\}\,,\\ \nu \cdot \frac{\nabla v}{\left|\nabla v \right|}&=& \cos \gamma_1 \qquad \textrm{on } y=f_1(x)\,,\\ \nu \cdot \frac{\nabla v}{\left|\nabla v \right|}&=& \cos \gamma_2 \qquad \textrm{on } y=f_2(x)\,, \end{eqnarray} exhibits sixth order asymptotic accuracy to the capillary equations~\eqref{0.1}$-$\eqref{0.3} near a circular cusp. Finally, we show that the solution is bounded and can be defined to be continuous at a symmetric cusp ($f_1(x)=-f_2(x)$) with the supplementary contact angles ($\gamma_2=\pi-\gamma_1$). Also it is shown that the solution surface is of the order $O\left(f_1(x)\right)$, and moreover, the formal asymptotic series for a symmetric circular cusp region is derived.

¡@¡@In recent years, the geographic information system (GIS) databases develop quickly and play a significant role in many applications. Many of these applications allow users to find objects with keywords and spatial information at the same time. Most researches in the spatial keyword queries only consider the exact match between the database and query with the textual information. Since users may not know how to spell the exact keyword, they make a query with the approximate-keyword, instead of the exact keyword. Therefore, how to process the approximate-keyword query in the spatial database becomes an important research topic. Alsubaiee et al. have proposed the Location-Based-Approximate-Keyword-tree (LBAK-tree) index structure which is to augment a tree-based spatial index with approximate-string indexes such as a gram-based index. However, the LBAK-tree index structure is the R*-tree based index structure. The nodes of the R*-tree have to be split and be reinserted when they get full. Due to this condition, it can not index the spatial attribute and the textual attribute at the same time. It stores the keywords in the nodes after the R*-tree is already built. Based on the R*-tree, it has to search all the children in a node to insert a new item and answer a query. Moreover, after they find the needed keywords by using the approximate index, they probe the nodes by checking the intersection of the similar keyword sets and the keywords stored in the nodes. However, the higher level the node is, the larger the number of keywords stored in the node is. It takes long time to check the intersections. And the LBAK-tree checks all the intersections even if there exits one of the intersections which is already an empty set. Therefore, in this thesis, we propose the Nine-Area-Approximate-Keyword-tree (NAAK-tree) index structure to process the spatial approximate-keyword query. We do not have to partition the space to construct the spatial index. We do not have to reinsert the children when split the nodes, so we can deal with the keywords at the same time. We can use the spatial number to find out the nodes that satisfy the spatial condition of the query. And we augment the NAAK-tree with signatures to speed up the query of the textual condition. We use the union of the bit strings of each keyword in a node to represent them in the node. Therefore, we can efficiently filter out the nodes that there is no keyword corresponding to the query by checking the signatures just one time without checking all the keywords stored in the nodes. Based on our NAAK-tree, if there exits one empty set in the similar keywords sets, we do not check all the similar keywords sets. From our simulation results, we show that the NAAK-tree is more efficient than the LBAK-tree to build the index and answer the spatial approximate-keyword query.

In this paper we consider the exact $D$-optimal design problem for linear trigonometric regression models with or without intercept on a partial circle. In a recent papper Dette, Melas and Pepelyshev (2001) found explicit solutions of approximate $D$-optimal designs for trigonometric regression models with intercept on a partial circle. The exact optimal designs are determined by means of moment sets of trigonometric functions. It is shown that the structure of the optimal designs depends on both the length of the design interval and the number of the design points.

No description available.

This report presents a weighted version of the Byzantine Agreement Problem and its solution under various conditions. In this version, each machine is assigned a weight depending on the application. Instead of assuming that at most $f$ out of $N$ machines fail, the algorithm assumes that the total weight of the machines that fail is at most $\rho < 1/3.$ When each machine has weight $1/N,$ this problem reduces to the standard Byzantine Generals Agreement Problem. By choosing weights appropriately, the weighted Byzantine Agreement Problem can be applied to situations where a subset of processes are more trusted. By using weights, the system can reach consensus in the presence of Byzantine failures, even when more than $N/3$ processes fail, so long as the total weight of the failed processes is less than $1/3.$ Some properties of the Weighted Byzantine Agreement algorithms when the weight vectors are not the same at every process are discussed. Also, a method to update the weights of the processes after execution of the weighted Byzantine Agreement is given. The update method guarantees that the weight of any correct process is never reduced and the weight of any faulty process, suspected by correct processes whose total weight is at least $1/4,$ is reduced to $0$ for future instances. A short discussion of some weight assignment strategies is also given. / text

Recent interest in approximate computation is driven by its potential to achieve large energy savings. We formally demonstrate an optimal way to reduce energy via voltage over-scaling at the cost of errors due to timing starvation in addition. A fundamental trade-off between error frequency and error magnitude in a timing-starved adder has been identified. We introduce a formal model to prove that for signal processing applications using a quadratic signal-to-noise ratio error measure, reducing bit-wise error frequency is sub-optimal. Instead, energy-optimal approximate addition requires limiting maximum error magnitude. Intriguingly, due to possible error patterns, this is achieved by reducing carry chains significantly below what is allowed by the timing budget for a large fraction of sum bits, using an aligned, fixed internal-carry structure for higher significance bits. We further demonstrate that remaining approximation error is reduced by realization of conditional bounding (CB) logic for lower significance bits. A key contribution is the formalization of an approximate CB logic synthesis problem that produces a rich space of Pareto-optimal adders with a range of quality-energy trade-offs. We show how CB logic can be customized to result in over- and under-estimating approximate adders, and how a dithering adder that mixes them produces zero-centered error distributions, and, in accumulation, a reduced-variance error. This work demonstrates synthesized approximate adders with energy up to 60% smaller than that of a conventional timing-starved adder, where a 30% reduction is due to the superior synthesis of inexact CB logic. When used in a larger system implementing an image-processing algorithm, energy savings of 40% are possible. / text

For decades, the semiconductor industry enjoyed exponential improvements in microprocessor power and performance with the device scaling of successive technology generations. Scaling limitations at sub-micron technologies, however, have ceased to provide these historical performance improvements within a limited power budget. While device scaling provides a larger number of transistors per chip, for the same chip area, a growing percentage of the chip will have to be powered off at any given time due to power constraints. As such, the architecture community has focused on energy-efficient designs and is looking to specialized hardware to provide gains in performance. A focus on energy efficiency, along with increasingly less reliable transistors due to device scaling, has led to research in the area of approximate computing, where accuracy is traded for energy efficiency when precise computation is not required. There is a growing body of approximation-tolerant applications that, for example, compute on noisy or incomplete data, such as real-world sensor inputs, or make approximations to decrease the computation load in the analysis of cumbersome data sets. These approximation-tolerant applications span application domains, such as machine learning, image processing, robotics, and financial analysis, among others. Since the advent of the modern processor, computing models have largely presumed the attribute of accuracy. A willingness to relax accuracy requirements, however, with goal of gaining energy efficiency, warrants the re-investigation of the potential of analog computing. Analog hardware offers the opportunity for fast and low-power computation; however, it presents challenges in the form of accuracy. Where analog compute blocks have been applied to solve fixed-function problems, general-purpose computing has relied on digital hardware implementations that provide generality and programmability. The work presented in this thesis aims to answer the following questions: Can analog circuits be successfully integrated into general-purpose computing to provide performance and energy savings? And, what is required to address the historical analog challenges of inaccuracy, programmability, and a lack of generality to enable such an approach? This thesis work investigates a neural approach as a means to address the historical analog challenges of inaccuracy, programmability, and generality and to enable the use of analog circuits in general-purpose, high-performance computing. The first piece of this thesis work investigates the use of analog circuits at the microarchitecture level in the form of an analog neural branch predictor. The task of branch prediction can tolerate imprecision, as roll-back mechanisms correct for branch mispredictions, and application-level accuracy remains unaffected. We show that analog circuits enable the implementation of a highly-accurate, neural-prediction algorithm that is infeasible to implement in the digital domain. The second piece of this thesis work presents a neural accelerator that targets approximation-tolerant code. Analog neural acceleration provides application speedup of 3.3x and energy savings of 12.1x with a quality loss less than 10% for all except one approximation-tolerant benchmark. These results show that, using a neural approach, analog circuits can be applied to provide performance and energy efficiency in high-performance, general-purpose computing. / text

Energy minimization has become an ever more important concern in the design of very large scale integrated circuits (VLSI). In recent years, approximate computing, which is based on the idea of trading off computational accuracy for improved energy efficiency, has attracted significant attention. Applications that are both compute-intensive and error-tolerant are most suitable to adopt approximation strategies. This includes digital signal processing, data mining, machine learning or search algorithms. Such approximations can be achieved at several design levels, ranging from software, algorithm and architecture, down to logic or transistor levels. This dissertation investigates two research threads for the derivation of approximate digital circuits at the logic level: 1) modeling and synthesis of fundamental arithmetic building blocks; 2) automated techniques for synthesizing arbitrary approximate logic circuits under general error specifications. The first thread investigates elementary arithmetic blocks, such as adders and multipliers, which are at the core of all data processing and often consume most of the energy in a circuit. An optimal strategy is developed to reduce energy consumption in timing-starved adders under voltage over-scaling. This allows a formal demonstration that, under quadratic error measures prevalent in signal processing applications, an adder design strategy that separates the most significant bits (MSBs) from the least significant bits (LSBs) is optimal. An optimal conditional bounding (CB) logic is further proposed for the LSBs, which selectively compensates for the occurrence of errors in the MSB part. There is a rich design space of optimal adders defined by different CB solutions. The other thread considers the problem of approximate logic synthesis (ALS) in two-level form. ALS is concerned with formally synthesizing a minimum-cost approximate Boolean function, whose behavior deviates from a specified exact Boolean function in a well-constrained manner. It is established that the ALS problem un-constrained by the frequency of errors is isomorphic to a Boolean relation (BR) minimization problem, and hence can be efficiently solved by existing BR minimizers. An efficient heuristic is further developed which iteratively refines the magnitude-constrained solution to arrive at a two-level representation also satisfying error frequency constraints. To extend the two-level solution into an approach for multi-level approximate logic synthesis (MALS), Boolean network simplifications allowed by external don't cares (EXDCs) are used. The key contribution is in finding non-trivial EXDCs that can maximally approach the external BR and, when applied to the Boolean network, solve the MALS problem constrained by magnitude only. The algorithm then ensures compliance to error frequency constraints by recovering the correct outputs on the sought number of error-producing inputs while aiming to minimize the network cost increase. Experiments have demonstrated the effectiveness of the proposed techniques in deriving approximate circuits. The approximate adders can save up to 60% energy compared to exact adders for a reasonable accuracy. When used in larger systems implementing image-processing algorithms, energy savings of 40% are possible. The logic synthesis approaches generally can produce approximate Boolean functions or networks with complexity reductions ranging from 30% to 50% under small error constraints. / text

The thesis focuses on a model that seeks to address patient scheduling step of the surgical scheduling process to determine the number of surgeries to perform in a given day. Specifically, provided a master schedule that provides a cyclic breakdown of total OR availability into specific daily allocations to each surgical specialty, we look to provide a scheduling policy for all surgeries that minimizes a combination of the lead time between patient request and surgery date, overtime in the ORs and congestion in the wards. We cast the problem of generating optimal control strategies into the framework of Markov Decision Process (MDP). The Approximate Dynamic Programming (ADP) approach has been employed to solving the model which would otherwise be intractable due to the size of the state space. We assess performance of resulting policy and quality of the driven policy through simulation and we provide our policy insights and conclusions.