Recovering network connectivity structure from high-dimensional observations is of increasing importance in statistical learning applications. A prominent approach is to learn a Sparse Gaussian Markov Random Field by optimizing regularized maximum likelihood, where the sparsity is induced by imposing L1 norm on the entries of a precision matrix. In this article, we shed light on an alternative objective, where instead of precision, its Cholesky factor is penalized by the L1 norm. We show that such an objective criterion possesses attractive properties that allowed us to develop a very fast Scale-Free Networks Estimation Through Cholesky factorization (SNETCH) optimization algorithm based on coordinate descent, which is highly parallelizable and can exploit an active set approach. The approach is particularly suited for problems with structures that allow sparse Cholesky factor, an important example being scale-free networks. Evaluation on synthetically generated examples and high-impact applications from a biomedical domain of up to more than 900,000 variables provides evidence that for such tasks the SNETCH algorithm can learn the underlying structure more accurately, and an order of magnitude faster than state-of-the-art approaches based on the L1 penalized precision matrix.

Learning the sparse Gaussian Markov Random Field, or conversely, estimating the sparse inverse covariance matrix is an approach to uncover the underlying dependency structure in data. Most of the current methods solve the problem by optimizing the maximum likelihood objective with a Laplace prior L1 on entries of a precision matrix. We propose a novel objective with a regularization term which penalizes an approximate product of the Cholesky decomposed precision matrix. This new reparametrization of the penalty term allows efficient coordinate descent optimization, which in synergy with an active set approach results in a very fast and efficient method for learning the sparse inverse covariance matrix. We evaluated the speed and solution quality of the newly proposed SCHL method on problems consisting of up to 24,840 variables. Our approach was several times faster than three state-of-the-art approaches. We also demonstrate that SCHL can be used to discover interpretable networks, by applying it to a high impact problem from the health informatics domain.

Recently proposed hybrid dataflow and shared memory programming models combine these two underlying models in order to support a wider range of problems naturally. The effectiveness of such hybrid models for parallel implementations of dense and sparse algebra problems is well known. In this paper, we show another real world example for which hybrid dataflow models provide better support than traditional shared memory models. Specifically, we compare these models using the game engine parallelization as a case study. We show that hybrid dataflow models decrease the complexity of the parallel game engine implementation by eliminating or restructuring the explicit synchronization that is necessary in shared memory implementations. The corresponding implementations also exhibit good scala-bility and better speedup than the shared memory parallel implementations, especially in the case of a highly congested game world that contains a large number of game objects. Ultimately, on an eight core machine we were able to obtain 4.72x speedup compared to the sequential baseline, and to improve 49% over the lock-based parallel implementation based on work-sharing.

In spite of great developments in artificial intelligence, human brain is still more powerful, concerning the comprehension and manipulation with partially known facts. One domain where this is prominent is related to a problem of question answering. When it comes to giving the answers, especially those that do not explicitly exist in the text corpus, the advantages of a human expert are abilities such as explaining, combining complex answers, and abstract reasoning. This paper represents a survey of the existing research in the domain of intelligent question routing. The survey starts from an original presentation paradigm that generalizes the essence of approaches found in the open literature. The presentation paradigm includes three basic processing stages related to the three major problems of system implementation: question analysis, question forwarding, and users’ knowledge profiling. Various research efforts use different approaches for implementation of each one of the basic processing stages. Each particular approach is described here using the same template. All these approaches are enlisted, discussed, and presented within a table, for easier comparison. The outcome of this analysis is a proposal for a new approach that tackles identified problems.

This article presents a new Fast Hash-based File Existence Checking (FHFEC) method for archiving systems. During the archiving process, there are many submissions which are actually unchanged files that do not need to be re-archived. In this system, instead of comparing the entire files, only digests of the files are compared. Strong cryptographic hash functions with a low probability of collision can be used as digests. We propose a fast algorithm to check if a certain hash, that is, a corresponding file, is already stored in the system. The algorithm is based on dividing the whole domain of hashes into equally sized regions, and on the existence of a pointer array, which has exactly one pointer for each region. Each pointer points to the location of the first stored hash from the corresponding region and has a null value if no hash from that region exists. The entire structure can be stored in random access memory or, alternatively, on a dedicated hard disk. A statistical performance analysis has been performed that shows that in certain cases FHFEC performs nearly optimally. Extensive simulations have confirmed these analytical results. The performance of FHFEC has been compared to the performance of a binary search (BIS) and B+tree, which are commonly used in file systems and databases for table indices. The results show that FHFEC significantly outperforms both of them.

Extracting and processing information from Web pages is an important task in many areas like constructing search engines, information retrieval, and data mining from the Web. A common approach in the extraction process is to represent a page as a "bag of words" and then to perform additional processing on such a flat representation. We propose a new, hierarchical representation that includes browser screen coordinates for every HTML object in a page. Using visual information one is able to define heuristics for the recognition of common page areas such as header, left and right menu, footer and center of a page. We show in initial experiments that using our heuristics defined objects are recognized properly in 73% of cases. Finally, we show that a Naive Bayes classifier, taking into account the proposed representation, clearly outperforms the same classifier using only information about the content of documents.

The paper introduces a new approach to acceleration of nonnumeric, database, and information retrieval operations. While traditional techniques accelerate the most time-critical high-level software constructs, we propose novel low-level primitives and demonstrate how these primitives improve database operations. Radix sorting, hashing, and bit-vector operations are used to develop a new class of nonnumeric algorithms - OTHER (Ordered Table Hashing and Radix sort algorithms) - based on low-level hashing operations Init, Mark, and Scan. We have proposed and evaluated two hardware accelerators for OTHER algorithms. It is shown that a low complexity hardware support (less than 10 K transistors) can significantly improve the performance of nonnumeric operations.

We consider the problem of synthesizing multiple-valued logic functions by neural networks. A genetic algorithm (GA) which finds the longest strip in V is a subset of K(n) is described. A strip contains points located between two parallel hyperplanes. Repeated application of GA partitions the space V into certain number of strips, each of them corresponding to a hidden unit. We construct two neural networks based on these hidden units and show that they correctly compute the given but arbitrary multiple-valued function. Preliminary experimental results are presented and discussed.

Concentrates on the problem of defining and measuring parameters that characterize typical behavior of parallel applications targeted to distributed shared memory (DSM) systems and shared-memory multiprocessors (SMPs). These parameters can be used as input to various models for performance evaluation in this research area. Furthermore, typical application behaviors can be recognized, which can help to generate new ideas for improvements to memory consistency protocols, adapting them to specific application characteristics. Our study encompasses a variety of parameters, such as frequencies of operations of various access types (private read/writes, shared read/writes, lock operations, barrier operations), the average number of accessed blocks per interval, the average number of modified words, etc. The results presented in this paper are based on the SPLASH-2 (Stanford Parallel Applications for SHared Memory) application suite. The developed instrumentation tool Scowl, along with the applied simulation environment Limes, are publicly available and applicable for performing measurements on other parallel applications as well.

In a distributed shared memory (DSM) system that implements an entry consistency model, shared data must be explicitly associated to a synchronization variable, and it can be accessed only in critical sections protected by that specific synchronization variable. The authors propose three protocols for entry consistency maintenance, ECU, ECI, and ECHBP, and they identify costs introduced by each of these consistency protocols, such as communication, processing and synchronization latencies. In order to determine synchronization latency we use a modified version of the MVA algorithm, while communication and processing latencies depend on an application's access behavior expressed by a probabilistic model. Finally, we determine processing power (e.g. speedup) of a system with N processors, taking into account communication, processing and synchronization latencies. In this way, we build a model for analytical comparison of the proposed protocols for a wide range of input parameters.

——————————F—————————— HE concept of cache memory has emerged as a solution for the ever increasing time domain gap between processor technology and memory technology. Since the very early works of Wilkes [13], the concept has evolved into a sophisticated system of hardware-implemented and software-implemented solutions. Actually, the best performance/complexity ratio is obtained through a synergistic interaction of hardware-based and software-based solutions. The efficiency of the caching system is achieved through appropriate exploitation of the principles of temporal and spatial locality. Traditionally, temporal locality means that the probability is relatively high that a data or an instruction item will be reused in the near future. Spatial locality means that the probability is relatively high that the next data or instruction item to be used is in some way neighboring the previously used data or instruction item. In traditional systems, temporal locality is exploited by keeping some of the most recently used data/instructions in the cache memory and by incorporating the cache hierarchy. Spatial locality is exploited by using larger cache blocks and by incorporating the prefetching mechanisms into the caching system. As technology gets more and more sophisticated, it has become obvious that a much better performance can be achieved through the incorporation of more sophisticated solutions for enhancing and exploiting of the locality present in the code or data. As microprocessors get more and more complex, cache design and performance become more and more impacted by the solutions utilized in other domains, like superpipelining, superscaling, multithreading, prediction, parallelization, etc. Implementation issues in modern microprocessor systems are getting new dimensions. The issues of most

Utility telemetry service allows utility providers to minimize their expenses and maximize service quality and competitiveness, using public switched telephone networks. The newly emerging IEEE standard 1390 defines alert signals for network to telemetry interface, which activate the telemetry interface unit. Since this standard is on a relatively specific subject, VLSI detectors for the IEEE 1390 signals are not widespread on the market. Instead of using optimal detection methods, a detector of these signals is suggested here, based on suboptimal detection methods. The analysis has been performed in several steps: (a) mathematical modeling, (b) simulation analysis, and (c) implementation analysis. The performed analysis indicates that suboptimal methods offer satisfactory performance, even with a relatively large quantization noise, which implies lower VLSI complexity and production cost.

Software-controlled cache prefetching and data forwarding are widely used techniques for tolerating memory latency in shared memory multiprocessors. However, some previous studies show that cache prefetching is not so effective on bus-based multiprocessors, while the effectiveness of data forwarding has not been explored in this environment, yet. In this paper, a novel technique called cache injection is proposed. Cache injection, tuned to the properties of bus-based architectures, combines advantages of both cache prefetching and data forwarding. Some preliminary experiments show that the proposed solution can significantly help in reducing the overall miss ratio and bus traffic in applications where write-shared data prevails.

Branch misprediction is one of the important causes of performance degradation in superpipelined and superscalar processors. Most of the existing branch predictors, based on the exploiting of branch history, suffer from prediction accuracy decrease caused by frequent context switches. The goal of this research is to reduce misprediction rate (MPR) when the context switches are frequent, and not to increase the MPR when the context switches are relatively rare. We propose two independent, but closely related modifications of global adaptive prediction mechanisms: first, to flush only the branch history register (BHR) at context switch, instead of reinitialization of the whole predictor, and second, to use two separated BHRs, one for user and one for kernel branches, instead of one global history register. We have evaluated the ideas by measurements on real traces from IBS (Instruction Benchmark Set), and have shown that both modifications reduce MPR at negligible hardware cost.

The paper presents solutions for an element of the cluster that will be primarily used as a scalable storage product for a collection of mainframes. Existing storage solutions either employ server attached disks: where the problem is the number of I/O slots, or are specially designed products where the problem is the lack of standards. The essence of both proposed solutions is the introduction of the file usage locality concept, together with methods and techniques to exploit it. The first solution is based on the standard SMP architecture, while the second one employs the DSM architecture as the basic building block of a cluster product.

One of the major problems in a number of SM (shared memory) and DSM (distributed shared memory) applications is the overall cost of read misses in conditions when: (a) system latencies are relatively large, and (b) a shared data item is read relatively few times by each of the processors in the system; modern SM and DSM systems are typically based on off-the-shelf microprocessors which do not include any support for the described problem. Consequently, the major goal of our research is to come up with a new concept to be incorporated into the next generation microprocessors, so they can became more efficient in the sense described above. Existing 64-bit processors support only data prefetching (PF) as a method to fight against negative effects of the described problem. Our research introduces a new concept referred to as cache injection (CI), as well as the related cache injection/cofetch architecture (CICA). Initial performance evaluation is performed using a simulation methodology based on the set of synthetic benchmarks.

This survey of heterogeneous computing concepts and systems is based on the recently proposed by the authors "EM/sup 3/ " (Execution Modes/Machine Models) taxonomy of computer systems in general. The taxonomy is based on two criteria: the number of execution modes supported by the system and the number of machine models present in the system. Since these two criteria are orthogonal, four classes exist: Single Execution mode/Single machine Model (SESM), Single Execution modes/Multiple machine Models (SEMM), Multiple Execution modes/Single machine Model (MESM), and Multiple Execution modes/Multiple machine Models (MEMM). In Section II, heterogeneous computing concepts are viewed through three phases of the compilation and execution of any heterogeneous application: parallelism detection, parallelism characterization and resource allocation. Parallelism detection phase discovers fine-grain parallelism inside every task. This phase is not an exclusive feature of heterogeneous computing, so it will not be dealt with in greater detail. The assignment of parallelism characterization phase is to estimate the behavior of each task in the application on every architecture in the heterogeneous system. In the parallelism characterization domain, one original taxonomy is given. This taxonomy contains scheme classes such as vector and matrix static and dynamic, implicit and explicit, algorithmic and heuristic and numeric and symbolic. Resource allocation phase determines the place and the moment for execution of every task to optimize certain performance measure related to some criteria. In the resource allocation domain, the existing Casavant-Kuhl taxonomy is extended and used. This well known taxonomy is supplemented with scheme classes such as noncooperative competitive, noncooperative noncompetitive, and load sharing. In Section III, heterogeneous systems characterized with multiple execution modes ("fully" heterogeneous systems falling in the MESM and the MEMM class) are surveyed. The MESM class systems are described and illustrated with three case studies, two of which support SIMD/MIMD and one supports scalar/vector combination of execution modes. The MEMM class systems are described and illustrated with two representative examples of fully heterogeneous networks supporting multiple execution modes. The system software for heterogeneous computing systems is presented according to an original three-dimensional (3-D) taxonomy whose criteria rely on the level of heterogeneity support implementation, the programming approach, and the data access technique applied. In Section III, several representative heterogeneous applications are described with their computation requirements and the systems used for their execution. Each topic covered in the paper contains several concise examples.

The results of a study of the instruction pipeline design for a 32-b single-chip GaAs microprocessor are presented. The authors introduce nine candidate solutions for the instruction pipeline, define a set of technology-dependent and application-related parameters, and present the results of the comparative performance evaluation. Important differences between GaAs and silicon, which are relevant for the design of an instruction pipeline, are described. The authors determine the quantitative differences between various candidate solutions. The superb performance of the pipelined memory pipeline in all environments is demonstrated.>

The problem of how to assess the probability distribution function (PDF) of the propagation delay for different adder types in order to compare their sensitivities to stochastic changes of gate delays is addressed. An original methodology that solves the problem for combinational circuits of arbitrary topology (without loops) is introduced. Its capabilities are demonstrated through the modeling and analysis of propagation delays in GaAs adders. This methodology is directly applicable to a number of analogous problems in other fields.>

The use of the Honeycomb architecture for the implementation of neural networks in the next generation of supercomputers is discussed. The major point is that the relative value of various neural network models depends heavily on the chosen implementation technology. Models that are superior when it comes to conventional implementation architectures and related technologies may be inferior if the Honeycomb architecture and related technologies are used, and vice versa.>

The design of RCA's 32-bit GaAs microprocessor is described. Technology limitations and influences of the software environment are discussed. The details of the instruction set architecture (ISA) and the instruction execution sequence (IES) are described. The essence of the original contributions of the research and the design is emphasized. The simulated performance evaluation data are presented.>

The authors concentrate on design tradeoffs between the bit-serial multiplier and the full barrel shifter combined with a large register file. They analyze and compare three alternatives for a given set of technology related parameters and a given set of higher level language (HLL) benchmarks. Although their basic concern is the design of a 32-bit GaAs microprocessor on a single chip, the implications of the results are more general.>

A comparison is made of the performance of three algorithms for suboptimal signal detection applied to an additive mix of orthogonal sinusoidal signals. The study considers zero-mean Gaussian noise and a number of different impairments found in related data communications media, including quantization effects, frequency-selective fading, and frequency shifts. It is shown that different procedures ran differently in the presence of different impairments, so that the final selection of the procedure to be implemented will depend on the characteristics of the communications environment.>

The authors concentrate on the simulation study of two distributed task allocation procedures: the load balancing and the LOCO procedure. The first is widely used in general-purpose processing. The second was recently introduced and analyzed in the processing environment corresponding to the complex multitask jobs typical of some supercomputing and artificial-intelligence-oriented systems. Both procedures are simulated and compared in realistic situations, where both processing resources and interconnection network may represent the system bottleneck. Both were tested using carrier-sense multiple-access communications protocols. The CSMA/CD protocol performed better than TDMA with load balancing, but no difference was found with the LOCO procedure. For a large number of special-purpose processing resources and a large number of jobs in the system, LOCO produced better results than load balancing.>

This paper analyzes the potential performance of a high-level language (HLL) microprocessor architecture for special- purpose real-time applications. Our approach is based on mapping of HLL constructs into microcode, a concept called vertical migration. An analytical execution-time model of the reduced vertical-migration architecture is developed. It is applied to two different workload models: one corresponding to statement mixes, and the other showing some HLL kernel routines. Performance evaluation results are compared to different forms of the reduced vertical-migration architecture, and in various application domains. We underline in this paper the, basic relationships among microprocessor architecture, GaAs technology, and real-time applications.

Vertical-migration microprocessor architecture was introduced in [1], and results of its analytical study were presented in the same paper. This paper presents results of its simulation study which is based on selected production benchmarks. Vertical-migration architecture enables the constructs typical of HLL's to be mapped into the constructs typical of microcode. This mapping is provided only for selected types of HLL statements and for HLL statements with a relatively small number of operands and parameters, i.e., for-the most frequent HLL constructs. Using an extended subset of Fortran 77, one that matches the typical demands of the targeted application, i.e., dedicated microprocessing, it has been shown how the proposed architecture supports the mapping of HLL constructs into microinstructions. That was done through the description of a flexible register-transfer level simulator which was implemented to support this study. It was used to run benchmarks, typical of various applications, on various configurations of the architecture. Simulation study has shown that this approach is particularly suitable for the time-critical dedicated signal processing and robotics/control applications, as well as for the GaAs implementation.

High-speed data communications over voice-band telephone lines is a research topic of increased importance today. The speed which is currently attracting most of interest is 14.4 Kbps. This paper gives a tutorial exposition of three algorithms for implementation of various functions in a 14.4 Kbps data modem: Trellis, Viterbi, and Decision-Feedback Equalization (DFE). The basic contribution of our work is in investigation of their computational complexity from the viewpoint of the implementation based on the Texas Instruments TMS320 microprocessor family. Our work is based on the earlier work of Ungerboeck [14], whose idea was to transmit N bits per signaling interval, with an+1-ary QAM constellation, and modulator symbols being determined by a short constraint length convolutional encoder. We also rely on the earlier work of Monsen [5] with respect to the Decision-Feedback equalization.

Adaptive equalization based on a transversal filter is extremely important for reliable data transmission over the voiceband telephone lines. Unfortunately, implementation of rapidly converging and small residual distortion algorithms on the standard MOS microprocessors or standard-cell MOS VLSI chips is difficult because of their mathematical complexity. In this paper, an adaptive equalization algorithm is proposed which is suitable for cost-effective implementation on MOS microprocessors and standard-cell MOS VLSI chips. It is based on the same principle of delayed decision that was used successfully in delta modulation. It involves no multiplications or analog-to-digital conversion, but is relatively fast and provides a relatively low residual distortion. The proposed algorithm is simulated in both noise-free and noisy environments and is compared to two well-known classical algorithms.

The microprocessor-based implementation of data modems has been attracting a great deal of scientific interest in the past decade. It is a kind of an interdisciplinary field where both information theory and microprocessor engineering strongly interact. A number of different microprocessor-based modems are avavilable on the market. For most of the modems with speeds above 2400 b/s it is common that implementation is based on the bit-slice processor. In case of speeds above 2400 b/s, it is considered that slow and cheap MOS microprocessors (e.g., Intel 8085) can be used only at the cost of simplifications in the algorithms for signal demodulation and detection, i.e., at the cost of decreased performance. This paper, however, describes the MOS microprocessor-based implementation of the 4800 b/s modem which was achieved without deterioration of modem performance.