This paper investigates the problem of nonpreemptively scheduling independent parallel tasks in an environment with multiple machines, which is motivated from the recent studies in scheduling tasks in a multi-machine environment. In this scheduling environment, each machine contains a number of identical processors and each parallel task can simultaneously require a number of processors for its processing in any single machine. Whenever tasks are processed in parallel in a parallel machine, message communication among processors is often inevitable. The problem of finding a shortest schedule length on scheduling independent parallel tasks with the consideration of communication overhead in a multi-machine environment is NP-hard. The aim of this paper is to propose a heuristic algorithm for this kind of problem and to analyze the performance bound of this heuristic algorithm.

Hierarchical approaches using multi-resolution images are well-known techniques to reduce the computational amount without degrading quality. One major issue in designing image processors is to design a memory system that supports parallel access with a simple interconnection network. The complexity of the interconnection network mainly depends on memory allocation; it maps pixels onto memory modules and determines the required number of memory modules. This paper presents a memory allocation method to minimize the number of memory modules for image processing using multi-resolution images. For efficient search, the proposed method exploits the regularity of window-type image processing. A practical example demonstrates that the number of memory modules is reduced to less than 14% that of conventional methods.

Managing increasing traffic from Instant Messengers and P2P applications is becoming more important nowadays. We present an in-kernel architecture of management gateway, namely kP2PADM, built upon open-source packages with several modifications and design techniques. First, the in-kernel design streamlines the data path through the gateway. Second, the dual-queue buffer eliminates head-of-line blocking for multiple connections. Third, a connection cache reduces useless reconnection attempts from the peers. Fourth, a fast-pass mechanism avoids slowing down the TCP transmission. The in-kernel design approximately doubles the throughput of the design in the user space. The internal benchmarks also analyze the impact of each function on performance.

One of the most well-studied problems in data mining is computing the collection of frequent itemsets in large transactional databases. Since the introduction of the famous Apriori algorithm [14], many others have been proposed to find the frequent itemsets. Among such algorithms, the approach of mining closed itemsets has raised much interest in data mining community. The algorithms taking this approach include TITANIC [8], CLOSET+ [6], DCI-Closed [4], FCI-Stream [3], GC-Tree [5], TGC-Tree [16] etc. Among these algorithms, FCI-Stream, GC-Tree and TGC-Tree are online algorithms work under sliding window environments. By the performance evaluation in [16], GC-Tree [15] is the fastest one. In this paper, an improved algorithm based on GC-Tree is proposed, the computational complexity of which is proved to be a linear combination of the average transaction size and the average closed itemset size. The algorithm is based on the essential theorem presented in Sect. 4.2. Empirically, the new algorithm is several orders of magnitude faster than the state of art algorithm, GC-Tree.

One of the major challenges facing the design of a routing protocol for Wireless Sensor Networks (WSNs) is to find the most reliable path between the source and sink node. Furthermore, a routing protocol for WSN should be well aware of sensor limitations. In this paper, we present an energy efficient, scalable, and distributed node disjoint multipath routing algorithm. The proposed algorithm, the Energy-aware Multipath Routing Algorithm (EMRA), adjusts traffic flows via a novel load balancing scheme. EMRA has a higher average node energy efficiency, lower control overhead, and a shorter average delay than those of well-known previous works. Moreover, since EMRA takes into consideration network reliability, it is useful for delivering data in unreliable environments.

With the nano-scale technology, an system-on-chip (SOC) design may consist of many reusable cores from multiple sources. This causes that the complexity of SOC testing is much higher than that of conventional VLSI chip testing. One of the SOC test challenges is the test data reduction. This paper presents a multi-code compression (MCC) technique to reduce the volume of test data and the test application time. A multi-code decompressor for recovering the compressed test data is also proposed. Experimental results show that the MCC scheme can achieve higher compression ratio than single-code compression schemes. The area cost of the proposed multi-code decompressor is small--only about 3498 µm² based on TSMC 0.18 µm standard cell technology.

Data compression is popularly applied to computer systems and communication systems in order to reduce storage size and communication time, respectively. Since large data are used frequently, string matching for such data takes a long time. If the data are compressed, the time gets much longer because decompression is necessary. Long string matching time makes computer virus scan time longer and gives serious influence to the security of data. From this, CPM (Compression Pattern Matching) methods for several compression methods have been proposed. This paper proposes CPM method for PPM which achieves fast virus scan and improves dependability of the compressed data, where PPM is based on a Markov model, uses a context information, and achieves a better compression ratio than BW transform and Ziv-Lempel coding. The proposed method encodes the context information, which is generated in the compression process, and appends the encoded data at the beginning of the compressed data as a header. The proposed method uses only the header information. Computer simulation says that augmentation of the compression ratio is less than 5 percent if the order of the PPM is less than 5 and the source file size is more than 1 M bytes, where order is the maximum length of the context used in PPM compression. String matching time is independent of the source file size and is very short, less than 0.3 micro seconds in the PC used for the simulation.

Rapid advances in semiconductor manufacturing technology have led to higher chip power densities, which places greater emphasis on packaging and temperature control during testing. For system-on-chips, peak power-based scheduling algorithms have been used to optimize tests under specified power constraints. However, imposing power constraints does not always solve the problem of overheating due to the non-uniform distribution of power across the chip. This paper presents a TAM/Wrapper co-design methodology for system-on-chips that ensures thermal safety while still optimizing the test schedule. The method combines a simplified thermal-cost model with a traditional bin-packing algorithm to minimize test time while satisfying temperature constraints. Furthermore, for temperature checking, thermal simulation is done using cycle-accurate power profiles for more realistic results. Experiments show that even a minimal sacrifice in test time can yield a considerable decrease in test temperature as well as the possibility of further lowering temperatures beyond those achieved using traditional power-based test scheduling.

The information technology revolution has transformed all aspects of our society including critical infrastructures and led a significant shift from their old and disparate business models based on proprietary and legacy environments to more open and consolidated ones. Supervisory Control and Data Acquisition (SCADA) systems have been widely used not only for industrial processes but also for some experimental facilities. Due to the nature of open environments, managing SCADA systems should meet various security requirements since system administrators need to deal with a large number of entities and functions involved in critical infrastructures. In this paper, we identify necessary access control requirements in SCADA systems and articulate access control policies for the simulated SCADA systems. We also attempt to analyze and realize those requirements and policies in the context of role-based access control that is suitable for simplifying administrative tasks in large scale enterprises.

This paper describes a method for recognizing romanized Japanese words in learner English. They become noise and problematic in a variety of systems and tools for language learning and teaching including text analysis, spell checking, and grammatical error detection because they are Japanese words and thus mostly unknown to such systems and tools. A problem one encounters when recognizing romanized Japanese words in learner English is that the spelling rules of romanized Japanese words are often violated. To address this problem, the described method uses a clustering algorithm reinforced by a small set of rules. Experiments show that it achieves an F-measure of 0.879 and outperforms other methods. They also show that it only requires the target text and an English word list of reasonable size.

In this paper, a new lifting-based shape-direction-adaptive discrete wavelet transform (SDA-DWT) which can be used for arbitrarily shaped segments is proposed. The SDA-DWT contains three major techniques: the lifting-based DWT, the adaptive directional technique, and the concept of object-based compression in MPEG-4. With SDA-DWT, the number of transformed coefficients is equal to the number of pixels in the arbitrarily shaped segment image, and the spatial correlation across subbands is well preserved. SDA-DWT also can locally adapt its filtering directions according to the texture orientations to improve energy compaction for images containing non-horizontal or non-vertical edge textures. SDA-DWT can be applied to any application that is wavelet based and the lifting technique provides much flexibility for hardware implementation. Experimental results show that, for still object images with rich orientation textures, SDA-DWT outperforms SA-DWT up to 5.88 dB in PSNR under 2.15-bpp (bit / object pixel) condition, and reduces the bit-budget up to 28.5% for lossless compression. SDA-DWT also outperforms DA-DWT up to 5.44 dB in PSNR under 3.28-bpp condition, and reduces the bit-budget up to 14.0%.

Point Pattern Matching (PPM) is an essential problem in many image analysis and computer vision tasks. This paper presents a two-stage algorithm for PPM problem using ellipse fitting and dual Hilbert scans. In the first matching stage, transformation parameters are coarsely estimated by using four node points of ellipses which are fitted by Weighted Least Square Fitting (WLSF). Then, Hilbert scans are used in two aspects of the second matching stage: it is applied to the similarity measure and it is also used for search space reduction. The similarity measure named Hilbert Scanning Distance (HSD) can be computed fast by converting the 2-D coordinates of 2-D points into 1-D space information using Hilbert scan. On the other hand, the N-D search space can be converted to a 1-D search space sequence by N-D Hilbert Scan and an efficient search strategy is proposed on the 1-D search space sequence. In the experiments, we use both simulated point set data and real fingerprint images to evaluate the performance of our algorithm, and our algorithm gives satisfying results both in accuracy and efficiency.

In this paper we present our investigation into improving the performance of our computer-assisted language learning (CALL) system through exploiting the acoustic model and features within the speech recognition framework. First, to alleviate channel distortion, speaker-dependent cepstrum mean normalization (CMN) is adopted and the average correlation coefficient (average CC) between machine and expert scores is improved from 78.00% to 84.14%. Second, heteroscedastic linear discriminant analysis (HLDA) is adopted to enhance the discriminability of the acoustic model, which successfully increases the average CC from 84.14% to 84.62%. Additionally, HLDA causes the scoring accuracy to be more stable at various pronunciation proficiency levels, and thus leads to an increase in the speaker correct-rank rate from 85.59% to 90.99%. Finally, we use maximum a posteriori (MAP) estimation to tune the acoustic model to fit strongly accented test speech. As a result, the average CC is improved from 84.62% to 86.57%. These three novel techniques improve the accuracy of evaluating pronunciation quality.

This paper describes a new color segmentation based on a normalized RGB chromaticity diagram for face detection. Face skin is extracted from color images using a coarse skin region with fixed boundaries followed by a fine skin region with variable boundaries. Two newly developed histograms that have prominent peaks of skin color and non-skin colors are employed to adjust the boundaries of the skin region. The proposed approach does not need a skin color model, which depends on a specific camera parameter and is usually limited to a particular environment condition, and no sample images are required. The experimental results using color face images of various races under varying lighting conditions and complex backgrounds, obtained from four different resources on the Internet, show a high detection rate of 87%. The results of the detection rate and computation time are comparable to the well known real-time face detection method proposed by Viola-Jones [11],[12].

Automatic adjustment methods for efficient, precise positioning and release of a virtual 3D object by direct hand manipulation in an immersive virtual reality environment are described and evaluated. The proposed methods are release adjustment, position adjustment, viewpoint adjustment, and virtual hand size adjustment. Combining these methods enables users to manipulate a virtual object efficiently and precisely. An experimental evaluation showed that these methods were effective and useful in terms of the number of task completions and the subjective preference, particularly for a small virtual target.

In this paper, we give some resuts on primitive words, square-free words and disjunctive languages. We show that for a word u ∈Σ⁺, every element of λ(cp(u)) is d-primitive iff it is square-free, where cp(u) is the set of all cyclic-permutations of u, and λ(cp(u)) is the set of all primitive roots of it. Next we show that p^mqⁿ is a primitive word for every n, m ≥1 and primitive words p, q, under the condition that |p| = |q| and (m, n) ≠ (1, 1). We also give a condition of disjunctiveness for a language.

The C-oscillation due to Martin-Löf shows that {α| ∀ n [C(α n)≥ n-O(1)]=, which also follows {α| ∀ n [K(α n)≥ n+K(n)-O(1)]=. By generalizing them, we show that there does not exist a real α such that ∀ n (K(α n)≥ n+λ K(n)-O(1)) for any λ>0.

MD5 is a cryptographic algorithm used for authentication. When implemented in hardware, the performance is affected by the data dependency of the iterative compression function. In this paper, a new functional description is proposed with the aim of achieving higher throughput by mean of reducing the critical path and latency. This description can be used in similar structures of other hash algorithms, such as SHA-1, SHA-2 and RIPEMD-160, which have comparable data dependence. The proposed MD5 hardware architecture achieves a high throughput/area ratio, results of implementation in an FPGA are presented and discussed, as well as comparisons against related works.

Vehicular ad hoc networks (VANET) aims to enhance vehicle navigation safety by providing an early warning system: any chance of accidents is informed through the wireless communication between vehicles. For the warning system to work, it is crucial that safety messages be reliably delivered to the target vehicles in a timely manner and thus reliable and timely data dissemination service is the key building block of VANET. Data mulling technique combined with three strategies, network codeing, erasure coding and repetition coding, is proposed for the reliable and timely data dissemination service. Particularly, vehicles in the opposite direction on a highway are exploited as data mules, mobile nodes physically delivering data to destinations, to overcome intermittent network connectivity cause by sparse vehicle traffic. Using analytic models, we show that in such a highway data mulling scenario the network coding based strategy outperforms erasure coding and repetition based strategies.

A residual acoustic echo cancellation method that employs the masking property is proposed to enhance the speech quality of hands-free communication devices in an automobile environment. The conventional masking property is employed for speech enhancement using the masking threshold of the desired clean speech signal. In this Letter, either the near-end speech or residual noise is selected as the desired signal according to the double-talk detector. Then, the residual echo signal is masked by the desired signal (masker). Experiments confirm the effectiveness of the proposed method by deriving the echo return loss enhancement and by examining speech waveforms and spectrograms.

In this paper, the simplified search designs for the stochastic codebook of algebraic code excited linear prediction (ACELP) for ITU-T G.729D speech coder are proposed. By using two search rounds and limiting the search range, the computational complexity of the proposed approach is only 6.25% of the full search method recommended by G.729D. In addition, the computational complexity of proposed approach is only 59% of the global pulse replacement search method recommended by G.729.1. Simulation results show that the coded speech quality evaluated by using the standard subjective and objective quality measurements is with perceptually negligible degradation.

This paper presents a text-independent speaker verification method using Gaussian mixture models (GMMs), where only utterances of enrolled speakers are required. Artificial cohorts are used instead of those from speaker databases, and GMMs for artificial cohorts are generated by changing model parameters of the GMM for a claimed speaker. Equal error rates by the proposed method are about 60% less than those by a conventional method which also uses only utterances of enrolled speakers.