The kernel-based regularization method has two core issues: kernel design and hyperparameter estimation. In this paper, we focus on the second issue and study the properties of several hyperparameter ...estimators including the empirical Bayes (EB) estimator, two Stein’s unbiased risk estimators (SURE) (one related to impulse response reconstruction and the other related to output prediction) and their corresponding Oracle counterparts, with an emphasis on the asymptotic properties of these hyperparameter estimators. To this goal, we first derive and then rewrite the first order optimality conditions of these hyperparameter estimators, leading to several insights on these hyperparameter estimators. Then we show that as the number of data goes to infinity, the two SUREs converge to the best hyperparameter minimizing the corresponding mean square error, respectively, while the more widely used EB estimator converges to another best hyperparameter minimizing the expectation of the EB estimation criterion. This indicates that the two SUREs are asymptotically optimal in the corresponding MSE senses but the EB estimator is not. Surprisingly, the convergence rate of two SUREs is slower than that of the EB estimator, and moreover, unlike the two SUREs, the EB estimator is independent of the convergence rate of ΦTΦ∕N to its limit, where Φ is the regression matrix and N is the number of data. A Monte Carlo simulation is provided to demonstrate the theoretical results.
The typical motion estimation (ME) consists of three main steps, including spatial-temporal prediction, integer-pel search, and fractional-pel search. The integer-pel search, which seeks the best ...matched integer-pel position within a search window, is considered to be crucial for video encoding. It occupies over 50% of the overall encoding time (when adopting the full search scheme) for software encoders, and introduces remarkable area cost, memory traffic, and power consumption to hardware encoders. In this paper, we find that video sequences (especially high-resolution videos) can often be encoded effectively and efficiently even without integer-pel search. Such counter-intuitive phenomenon is not only because that spatial-temporal prediction and fractional-pel search are accurate enough for the ME of many blocks. In fact, we observe that when the predicted motion vector is biased from the optimal motion vector (mainly for boundary blocks of irregularly moving objects), it is also hard for integer-pel search to reduce the final rate-distortion cost: the deviation of reference position could be alleviated with the fractional-pel interpolation and rate-distortion optimization techniques (e.g., adaptive macroblock mode). Considering the decreasing proportion of boundary blocks caused by the increasing resolution of videos, integer-pel search may be rather cost-ineffective in the era of high-resolution. Experimental results on 36 typical sequences of different resolutions encoded with x264, which is a widely-used video encoder, comply with our analysis well. For 1080p sequences, removing the integer-pel search saves 57.9% of the overall H.264 encoding time on average (compared to the original x264 with full integer-pel search using default parameters), while the resultant performance loss is negligible: the bit-rate is increased by only 0.18%, while the peak signal-to-noise ratio is decreased by only 0.01 dB per frame averagely.
Anomaly detection in large populations is a challenging but highly relevant problem. It is essentially a multi-hypothesis problem, with a hypothesis for every division of the systems into normal and ...anomalous systems. The number of hypothesis grows rapidly with the number of systems and approximate solutions become a necessity for any problem of practical interest. In this paper we take an optimization approach to this multi-hypothesis problem. It is first shown to be equivalent to a non-convex combinatorial optimization problem and then is relaxed to a convex optimization problem that can be solved distributively on the systems and that stays computationally tractable as the number of systems increase. An interesting property of the proposed method is that it can under certain conditions be shown to give exactly the same result as the combinatorial multi-hypothesis problem and the relaxation is hence tight.
Pre-Silicon Bug Forecast Guo, Qi; Chen, Tianshi; Chen, Yunji ...
IEEE transactions on computer-aided design of integrated circuits and systems,
2014-March, 2014-03-00, 20140301, Volume:
33, Issue:
3
Journal Article
Peer reviewed
Open access
The ever-intensifying time-to-market pressure imposes great challenges on the pre-silicon design phase of hardware. Before the tape-out, a pre-silicon design has to be thoroughly inspected by ...time-consuming functional verification and code review to exclude bugs. For functional verification and code review, a critical issue determining their efficiency is the allocation of resources (e.g., computational resources and manpower) to different modules of a design, which is conventionally guided by designers' experiences. Such practices, though simple and straightforward, may take high risks of wasting resources on bug-free modules or missing bugs in buggy modules, and thus could affect the success and timeline of the tape-out. In this paper, we propose a novel framework called pre-silicon bug forecast to predict the bug information of hardware designs. In this framework, bug models are built via machine learning techniques to characterize the relationship between design characteristics and the bug information, which can be leveraged to predict how bugs distribute in different modules of the current design. Such predicted bug information is adequate to regulate the resources among different modules to achieve efficient functional verification and code review. To evaluate the effectiveness of the proposed pre-silicon bug forecast framework, we conducted detailed experiments on several open-source hardware projects. Moreover, we also investigate the impacts of different learning techniques and different sets of characteristic on the performance of bug models. Experimental results show that with appropriate learning techniques and characteristics, about 90% modules could be correctly predicted as buggy or clean and the number of bugs of each module could also be accurately predicted.
Hyper-parameter estimation is a critical aspect of kernel-based regularization methods (KRMs), alongside kernel design. Empirical Bayes (EB) and Stein's unbiased risk estimator (SURE) are two widely ...used hyper-parameter estimators for tuning the unknown hyper-parameters associated with the kernel matrix of KRMs. However, EB and SURE exhibit different characteristics in both theory and practice. Theoretically, SURE is asymptotically optimal in terms of minimizing the mean squared error (MSE), whereas EB generally is not. However, practical evidence suggests that EB is often more accurate and robust than SURE, especially when the regression matrix is ill-conditioned. Therefore, this paper aims to deepen our understanding of these two estimators in a unified manner. Firstly, we construct a family of hyper-parameter estimators that encompasses both EB and SURE by introducing an index. We then explain the loss function of this family as a trade-off between data fit and model complexity for regularized least squares estimators, using least squares estimators as a reference. Secondly, we establish the convergence and rate of convergence of this family and further demonstrate that it is asymptotically optimal in some weighted MSE for a specific kernel matrix. Finally, Monte-Carlo simulations indicate the existence of other hyper-parameter estimators in this family that outperform both EB and SURE methods for certain datasets.
The state estimation problem for linear systems with linear state equality constraints was dealt with in Ko & Bitmead Ko, S., & Bitmead, R. (2007). State estimation for linear systems with state ...equality constraints. Automatica, 43, 1363–1368. In this correspondence, it is first shown that a necessary assumption on the covariance of the process noise is missing in the main result of the paper. It is then shown that the main result of the paper can be achieved in a convenient and more general way without any additional assumptions on the covariance of the process noise except positive definiteness.
In the last decade, kernel-based regularization methods (KRMs) have been widely used for stable impulse response estimation in system identification. Its favorable performance over classic maximum ...likelihood/prediction error methods (ML/PEM) has been verified by extensive simulations. Recently, we noticed a surprising observation: for some data sets and kernels, no matter how the hyper-parameters are tuned, the regularized least square estimate cannot have higher model fit than the least square (LS) estimate, which implies that for such cases, the regularization cannot improve the LS estimate. Therefore, this paper focuses on how to understand this observation. To this purpose, we first introduce the squared error (SE) criterion, and the corresponding oracle hyper-parameter estimator in the sense of minimizing the SE criterion. Then we find the necessary and sufficient conditions under which the regularization cannot improve the LS estimate, and we show that the probability that this happens is greater than zero. The theoretical findings are demonstrated through numerical simulations, and simultaneously the anomalous simulation outcome wherein the probability is nearly zero is elucidated, and due to the ill-conditioned nature of either the kernel matrix, the Gram matrix, or both. (c) 2023 Elsevier Ltd. All rights reserved.
Computation outsourcing using virtual appliance is getting prevalent in cloud computing. However, with both hardware and software being controlled by potentially curious or even malicious cloud ...operators, it is no surprise to see frequent reports of security accidents, like data leakages or abuses. This paper proposes Kite, a hardware-software framework that guards the security of tenant's virtual machine (VM), in which the outsourced computation is encapsulated. Kite only trusts the processor and makes no security assumption on external memory, devices, or hypervisor. Unlike prior hardware-based approaches, Kite retains transparency with existing VM and requires few changes to the (untrusted) hypervisor by introducing VM-Shim mechanism. Each VM-Shim instance runs in between its VM and the hypervisor, which only transfers necessary information designated by the VM to the hypervisor and external environments. Kite also considers the high-level semantic of interaction between VM and hypervisor to defend against attacks through legitimate operations or interfaces. We have implemented a prototype of Kite's secure processor in a QEMU-based full-system emulator and its software components on real machine. Evaluation shows that the performance overhead of Kite ranges from 0.5-14.0 percent on simulated platform and 0.4-7.3 percent on real hardware.
To efficiently and effectively debug silicon bugs, a promising solution is to determinize the chip, so that the buggy silicon behaviors can be faithfully reproduced on a RTL simulator. In this paper, ...we propose a novel scheme, named LDet, to determinize a chip through removing the nondeterminism in transfers crossing different clock domains, even when these clock domains are heterochronous. The key insight of LDet is that we can slightly adjust the frequencies of clocks at runtime so that the actual frequency ratio between two clocks always approaches a rational constant with bounded accumulated error. With the technique called dynamic frequency adjusting, the processing time of each asynchronous transfer can be determinized with deterministic asynchronous fifo (DAF). As a consequence, the behavior of the whole chip is deterministic, thus the chip behavior can be reproduced on the RTL simulator (given the same initial state and input sequence). We implement LDet on the RTL design of a processor chip with many clock domains. Experiments show that on average, LDet only causes about one cycle of additional latency to each asynchronous transfer. As a result, LDet only incurs a negligible performance overhead of about 0.7 percent slowdown. Moreover, LDet only brings less than 0.2 percent additional area to the chip. The low performance and area overheads of LDet well demonstrate its applicability in industry.
PDF
