6665649
My Brain is Full: When More Memory Helps
We consider the problem of finding good finite-horizon policies for POMDPs under the expected reward metric. The policies considered are free finite-memory policies with limited memory; a policy is a mapping from the space of observation-memory pairs to the space of action-memory pairs (the policy updates the memory as it goes), and the number of possible memory states is a parameter of the input to the policy-finding algorithms. The algorithms considered here are preliminary implementations of three search heuristics: local search. simulated annealing, and genetic algorithms. We compare their outcomes to each other and to the optimal policies for each instance. We compare run times of each policy and of a dynamic programming algorithm for POMDPs developed by Hansen that iteratively improves a finite-state controller - the previous state of the art for finite memory policies. The value of the best policy can only improve as the amount of memory increases, up to the amount needed for an optimal finite-memory policy. Our most surprising finding is that more memory helps in another way: given more memory than is needed for an optimal policy, the algorithms are more likely to converge to optimal-valued policies.
6096323
Quantifying instruction criticality for shared memory multiprocessors
Recent research on processor microarchitecture suggests using instruction criticality as a metric to guide hardware control policies. Fields et al. [3, 4] have proposed a directed acyclic graph (DAG) model for characterizing program microexecutions on uniprocessors. Under such a model, critical path analysis can be applied and instructions' slack values can be used to quantify instruction criticality. In this paper, we extend the uniprocessor DAG model to characterize parallel program executions on shared memory multiprocessor systems. We describe how critical path analysis can be applied, at a fine grain, in a multiprocessor system running both finite and continuous workloads. We provide detailed evaluations for various aspects of multiprocessor executions under the DAG model. To enable efficient offline critical path analysis, we propose a novel graph reduction technique that reduces a DAG to an equivalent but significantly smaller DAG.
10443056
A large, fast instruction window for tolerating cache misses
Instruction window size is an important design parameter for many modern processors. Large instruction windows offer the potential advantage of exposing large amounts of instruction level parallelism. Unfortunately naively scaling conventional window designs can significantly degrade clock cycle time, undermining the benefits of increased parallelism.This paper presents a new instruction window design targeted at achieving the latency tolerance of large windows with the clock cycle time of small windows. The key observation is that instructions dependent on a long latency operation (e.g., cache miss) cannot execute until that source operation completes. These instructions are moved out of the conventional, small, issue queue to a much larger waiting instruction buffer (WIB). When the long latency operation completes, the instructions are reinserted into the issue queue. In this paper, we focus specifically on load cache misses and their dependent instructions. Simulations reveal that, for an 8-way processor, a 2K-entry WIB with a 32-entry issue queue can achieve speedups of 20%, 84%, and 50% over a conventional 32-entry issue queue for a subset of the SPEC CINT2000, SPEC CFP2000, and Olden benchmarks, respectively.
17768597
A New Model for Dynamic Intrusion Detection
Building on the concepts and the formal definitions of self, nonself, antigen, and detector introduced in the research of network intrusion detection, the dynamic evolution models and the corresponding recursive equations of self, antigen, immune-tolerance, lifecycle of mature detectors, and immune memory are presented. Following that, an immune-based model, referred to as AIBM, for dynamic intrusion detection is developed. Simulation results show that the proposed model has several desirable features including self-learning, self-adaption and diversity, thus providing a effective solution for network intrusion detection.
15097946
Algorithms for clustering high dimensional and distributed data
Clustering is the problem of identifying the distribution of patterns and intrinsic correlations in large data sets by partitioning the data points into similarity classes. The clustering problem has been widely studied in machine learning, databases, and statistics. This paper studies the problem of clustering high dimensional data. The paper proposes an algorithm called the CoFD algorithm, which is a non-distance based clustering algorithm for high dimensional spaces. Based on the Maximum Likelihood Principle, CoFD attempts to optimize its parameter settings to maximize the likelihood between data points and the model generated by the parameters. The distributed versions of the problem, called the D-CoFD algorithms, are also proposed. Experimental results on both synthetic and real data sets show the efficiency and effectiveness of CoFD and D-CoFD algorithms.
2949388
Optimal k-Anonymity with Flexible Generalization Schemes through Bottom-up Searching
In recent years, a major thread of research on k-anonymity has focused on developing more flexible generalization schemes that produce higher-quality datasets. In this paper we introduce three new generalization schemes that improve on existing schemes, as well as algorithms enumerating valid generalizations in these schemes. We also introduce a taxonomy for generalization schemes and a new cost metric for measuring information loss. We present a bottom-up search strategy for finding optimal anonymizations. This strategy works particularly well when the value of k is small. We show the feasibility of our approach through experiments on real census data
206736471
Wavelet spectrum and its characterization property for random processes
The wavelet spectrum of a random process comprises the variances of the wavelet coefficients of the process computed within each scale. This paper investigates the possibility of using the wavelet spectrum, obtained from a continuous wavelet transform (CWT), to uniquely represent the second-order statistical properties of random processes-particularly, stationary processes and long-memory nonstationary processes. As is well known, the Fourier spectrum of a stationary process is mathematically equivalent to the autocovariance function (ACF) and thus uniquely determines the second-order statistics of the process. This characterization property is shown to be possessed also by the wavelet spectrum under very mild regularity conditions that are easily satisfied by many widely used wavelets. It is also shown that under suitable regularity conditions, the characterization property remains valid for processes with stationary increments including 1/f noise.
200438
Nanoparticle-enhanced proton computed tomography: a Monte Carlo simulation study
Proton computed tomography (pCT) has the potential to improve the accuracy of proton treatment planning, which is currently based on X-ray computed tomography (XCT). However, at this time no method exists for pCT to selectively increase the contrast of tumor tissues with respect to normal tissues. One possibility to achieve this goal is to bind gold-nanoparticles, i.e., microscopic structures in the size range of 1 nm to several hundred nanometers, to the surface of tumor cells with cell-seeking antibodies conjugated to the surface of the nanoparticles. In order to test the suitability of this approach, we used the Monte Carlo transport code GEANT4, to provide simulated histories of 200 MeV protons going through a cylindrical water phantom with embedded inhomogeneities enhanced with traces of gold. The energy loss of several million protons traversing the cylinder from 180 different angles formed the basis for reconstructing the single proton CT image representing the relative volume electron density map of the phantom using an approximate filtered back projection algorithm. Our results demonstrate that with hundred nanoparticles of 100 nm diameters per tumor cell, it may be possible to enhance the visibility of tumors in pCT.