REX is a reconfigurable experimental system for evaluating and developing parallel computer systems. It consists of large-scale FPGAs, and enables the systems to be reconfigured from their processors to the network topology in order to support their evaluation and development. We evaluated REX using several implementations of parallel computer systems, and showed that it had enough scalability of gates, memory throughput and network throughput. We also showed that REX was an effective tool because of its emulation speed and reconfigurability to develop systems.

The imprecise computation model is one of the flexible computation models used to construct real-time systems. It is especially useful when the worst case execution times are difficult to estimate or the execution times vary widely. Although there are several ways to implement this model, they have not attained much attentions of real-world application programmers to date due to their unrealistic assumptions and high dependency on the execution environment. In this paper, we present an integrated approach for implementing the imprecise computation model. In particular, our research covers three aspects. First, we present a new imprecise computation model which consists of a mandatory part, an optional part, and another mandatory part called wind-up part. This wind-up part allows application programmers to explicitly incorporate into their programs the exact operations needed for safe degradation of performance when there is a shortage in resources. Second, we describe a scheduling algorithm called Mandatory-First with Wind-up Part (M-FWP) which is based on the Earliest Deadline First strategy. This algorithm, unlike scheduling algorithms developed for the classical imprecise computation model, is capable of scheduling a mandatory portion after an optional portion. Third, we present a dynamic priority server method for an efficient implementation of the M-FWP algorithm. We also show that the number of the proposed server at most needed per node is one. In order to estimate the performance of the proposed approach, we have implemented a real-time operating system called RT-Frontier. The experimental analyses have proven its ability to implement tasks based on the imprecise computation model without requiring any knowledge on the execution time of the optional part. Moreover, it also showed performance gain over the traditional checkpointing technique.

The application of Elliptic Curve Cryptosystem has gained more and more attention. ECC uses smaller key size and lower memory requirement to retain the security level and can be a crucial factor in the smart card system. In this paper, an ECC based implementation of security schemes in smart card system to access control the door of some confidential places is proposed. The confidential place, for example a coffer, a strong room in the bank is used to store treasures as well as cashes, and where the mutual vigilance could be required. For the safety consideration, the going in and out a coffer by a person is not permissive but a group of authorized people. It involves the problem of secret sharing. The adopted solution of sharing secret is threshold scheme. Every participant possesses a secret shadow, which will be saved in the smart card. After correct reconstructing the shared secrets, it is permissible to access the coffer's door. For resisting dishonest participants, cheating detection and cheater identification will be included. The user can change his password of smart card freely and need not memorize his assigned lengthy password and shadow as traditional ID-based schemes makes our implementation much more user friendly.

In this paper, a new method is proposed to construct a visual secret sharing scheme with a general access structure for plural secret images. Although the proposed scheme can be considered as an extension of Droste's method that can encode only black-white images, it can encode plural gray-scale and/or color secret images.

Software rejuvenation is a proactive fault management technique that has been extensively studied in the recent literature. In this paper, we focus on an example for a telecommunication billing application considered in Huang et al. (1995) and develop the discrete-time stochastic models to estimate the optimal software rejuvenation schedule. More precisely, two software availability models with rejuvenation are formulated via the discrete semi-Markov processes, and the optimal software rejuvenation schedules which maximize the steady-state availabilities are derived analytically. Further, we develop statistically non-parametric algorithms to estimate the optimal software rejuvenation schedules, provided that the complete sample data of failure times are given. Then, a new statistical device, called the discrete total time on test statistics, is introduced. Finally, we examine asymptotic properties for the statistical estimation algorithms proposed in this paper through a simulation experiment.

In an optical time domain reflectometer type strain measurement system, we theoretically derive the shape of the Brillouin gain spectrum produced in an optical fiber under a parabolic strain distribution which is formed in a uniformly loaded beam. Based on the derived result, we investigate the effects of the parabolic strain distribution parameters and the measurement conditions such as the launched pulse width and the measurement position on the beam on the deformation of the Brillouin backscattered-light power spectrum shape. In addition, we investigate the strain measurement error resulting from the deformation of the power spectrum shape by analyzing the peak-power frequency at which the power spectrum is maximized.

In this paper, a high-performance pipelining architecture for 2-D inverse discrete wavelet transform (IDWT) is proposed. We use a tree-block pipeline-scheduling scheme to increase computation performance and reduce temporary buffers. The scheme divides the input subbands into several wavelet blocks and processes these blocks one by one, so the size of buffers for storing temporal subbands is greatly reduced. After scheduling the data flow, we fold the computations of all wavelet blocks into the same low-pass and high-pass filters to achieve higher hardware utilization and minimize hardware cost, and pipeline these two filters efficiently to reach higher throughput rate. For the computations of N N-sample 2-D IDWT with filter length of size K, our architecture takes at most (2/3)N2 cycles and requires 2N(K-2) registers. In addition, each filter is designed regularly and modularly, so it is easily scalable for different filter lengths and different levels. Because of its small storage, regularity, and high performance, the architecture can be applied to time-critical image decompression.

A distributor of digital contents desires to collect users' attributes. On the other hand, the users do not desire to offer the attributes owing to the privacy protection. Previously, an anonymous survey system for attributes statistics is proposed. In this system, asking trusted third parties' helps, a distributor can obtain the correct statistics of users' attributes, such as gender and age, while no information beyond the statistics is revealed. However, the system suffers from the inefficiency of a protocol to generate the statistics, since the cost depends on the number of all the users registering this survey system. This paper proposes an anonymous survey system, where this cost is independent from the number of all the registering users. In this accomplishment, a group signature scheme with attribute tracing is also proposed. A conventional group signature scheme allows a group member to anonymously sign a message on behalf of the group, while only a designated party can identify the signer. The proposed scheme further enables the party to trace signer's attribute.

Distributed configuration management involves maintaining a set of distributed storage and processing resources in such a way that they serve a community of users fairly, promptly, reliably and securely. Security has recently received much attention due to the general anxiety of hacking. Parallel computing systems such as clusters of workstations are no exception to this threat. This paper discusses experiments that measure the effect of employing randomisation in the scheduling of interdependent user and management tasks onto a distributed system such as clusters of workstations. Two attributes are investigated, namely performance and security. Performance is usually the prime objective in task scheduling. In this work the scheduling problem is viewed as a multi-objective optimisation problem where there is a subtle balance between efficient schedules and security. A schedule is secure if it is not vulnerable to malicious acts or inadvertent human errors. Further, the scheduling model should be hidden from unauthorised observers. The results of the study support the use of randomisation in the scheduling of tasks over an insecure network of processing nodes inhabited by malicious users.

In most cases of distributed memory computations, node programs are executed on processors according to the owner computes rule. However, owner computes rule is not best suited for irregular application codes. In irregular application codes, use of indirection in accessing left hand side array makes it difficult to partition the loop iterations, and because of use of indirection in accessing right hand side elements, we may reduce total communication by using heuristics other than owner computes rule. In this paper, we propose a communication cost reduction computes rule for irregular loop partitioning, called least communication computes rule. We partition a loop iteration to a processor on which the minimal communication cost is ensured when executing that iteration. Then, after all iterations are partitioned into various processors, we give global vs. local data transformation rule, indirection arrays remapping and communication optimization methods. The experimental results show that, in most cases, our approaches achieved better performance than other loop partitioning rules.

In this paper, we consider the all-to-all broadcast problem in optical broadcast star networks using Wavelength Division Multiplexing. Our network model assumes that receivers are fixed-tuned and transmitters are tunable such that optical lasers assigned to transmitters have limited access to the network bandwidth; hence, each node must be equipped with multiple optical lasers and/or multiple optical filters in order to maintain a single-hop network. This paper is primarily concerned with single-hop networks, in which each node is assigned a single optical filter. Lower bounds are first established on the number of lasers per each node and the minimum schedule length, and a schedule achieving the minimum schedule length is presented. The results are applicable to arbitrary tuning delays, arbitrary numbers of wavelength channels, and optical lasers' arbitrary tuning ranges. Network models with optical devices having limited tuning ranges have not yet been considered in connection with transmission schedules, and this is the first work in this new direction.

Most heuristics for the task scheduling problem employ a simple model of the target system, assuming fully connected processors, a dedicated communication subsystem and no contention for communication resources. A small number of algorithms is aware of the contention, using an undirected graph model of the communication network. Although, many scheduling algorithms have been compared in the literature, little is known about the accuracy and appropriateness of the employed models. This article evaluates the accuracy of task scheduling algorithms on generic parallel systems. The performed experiments show a significant inaccuracy of the schedules produced. In an extensive analysis, the reasons for these results are identified and the implications for the scheduling model are discussed.

Association mining extracts common relationships among a finite number of categorical data objects in a set of transactions. However, if the data objects are not categorical and potentially unlimited, it is impossible to employ the association mining approach. On the other hand, clustering is suitable for modeling a large number of non-categorical data objects as long as there exists a distance measure among them. Although it has been used to classify data objects in a data set into groups of similar objects based on data similarity, it can be used to extract the properties of similar data objects commonly appearing in a set of transactions. In this paper, a new clustering method, CLOCK, is proposed to find common knowledge such as frequent ranges of similar objects in a set of transactions. The common knowledge of data objects in the transactions can be represented by the occurrence frequency of similar data objects in terms of a transaction as well as the common repetitive ratio of similar data objects in each transaction. Furthermore, the proposed method also addresses how to maintain identified common knowledge as a summarized profile. As a result, any data difference between a newly collected transaction and the common knowledge of past transactions can be easily identified.

This paper proposes a new approach to fuzzy inference system for modeling nonlinear systems based on measured input and output data. In the suggested fuzzy inference system, the number of fuzzy rules and parameter values of membership functions are automatically decided by using the extended kernel method. The extended kernel method individually performs linear transformation and kernel mapping. Linear transformation projects input space into linearly transformed input space. Kernel mapping projects linearly transformed input space into high dimensional feature space. Especially, the process of linear transformation is needed in order to solve difficulty determining the type of kernel function which presents the nonlinear mapping in according to nonlinear system. The structure of the proposed fuzzy inference system is equal to a Takagi-Sugeno fuzzy model whose input variables are weighted linear combinations of input variables. In addition, the number of fuzzy rules can be reduced under the condition of optimizing a given criterion by adjusting linear transformation matrix and parameter values of kernel functions using the gradient descent method. Once a structure is selected, coefficients in consequent part are determined by the least square method. Simulated results of the proposed technique are illustrated by examples involving benchmark nonlinear systems.

Digital watermarking systems are required to embed as much information as possible in a digital media without the perceptual distortion as well as to extract it correctly with high probabilities, even though the media is subjected to many kinds of operations. To this end, guided scrambling (GS) techniques, usually used for a recording channel, are applied to digital watermarking systems. A simple GS scheme can make the power of a watermark signal larger against the power of media noise under the condition of preserving the perceptual fidelity, resulting in smaller error probabilities of the retrieved watermark bits. In addition, watermarking systems based on the GS can have more robustness to some specified operations if the prior information on the operations is given to the embedder. JPEG compression is a good example of such an operation when still images are transmitted over the Internet. In order for watermark signals to be more tolerable to the known JPEG attack, the GS-based watermark embedder is informed of advance knowledge of the JPEG compression. Further, a configuration of the GS concatenated with turbo coding is introduced to lower the bit error rate more.

It is shown that bounded impulse action can be combined with usual bang-bang control input to minimize the performance index. Especially for unstable oscillators, the size of controllable region can be increased. We present results on how to minimize the performance index using both ordinary bang-bang control and impulse actions with a recharge constraint on impulse firing. Following the maximum principle and necessary conditions induced from usual perturbation arguments, the mixed control input (bang-bang and impulse actions) is represented in adjoint state and then state variable feedback form. Simulation results show how the switch curves can be used to determine the optimal control value.

Applying gang scheduling can alleviate the blockade problem caused by exclusively used space-sharing strategies for parallel processing. However, the original form of gang scheduling is not practical as there are several fundamental problems associated with it. Recently many researchers have developed new strategies to alleviate some of these problems. Unfortunately, one important problem has not been so far seriously addressed, that is, how to set the length of time slots to obtain a good performance of gang scheduling. In this paper we present a strategy to deal with this important issue for efficient gang scheduling.

Within a few years it will be possible to integrate a billion transistors on a single chip operating at frequency more than 10 GHz. At this integration level, we propose using a multi-level ISA to express fine-grain data parallelism to hardware instead of using a huge transistor budget to dynamically extract it. Since the fundamental data structures for a wide variety of data parallel applications are scalar, vector, and matrix, our proposed Trident processor extends a scalar ISA with vector and matrix instruction sets to effectively process matrix formulated applications. Like vector architectures, the Trident processor consists of a set of parallel lanes (each lane contains a set of vector pipelines and a slice of register file) combined with a fast scalar core. However, Trident processor can effectively process on the parallel lanes not only vector but also matrix data. One key point of our architecture is the local communication within and across lanes to overcome the limitations of the future VLSI technology. Another key point is the effective execution of a mixture of scalar, vector, and matrix operations. This paper describes the architecture of the Trident processor and evaluates its performance on BLAS and on the standard matrix bidiagonalization algorithm. The last one is evaluated as an example of an entire application based on a mixture of scalar, vector, and matrix operations. Our results show that many data parallel applications, such as scientific, engineering, multimedia, etc., can be speeded up on the Trident processor. Besides, the scalability of the Trident processor does not require more fetch, decode, or issue bandwidth, but requires only replication of parallel lanes.

NK-Landscapes are stochastically generated fitness functions on bit strings, parameterized with N bits and K epistatic interactions between bits. The term epistasis describes nonlinearities in fitness functions due to changes in the values of interacting bits. Empirical studies have shown that the overall performance of random bit climbers on NK-Landscapes is superior to the performance of some simple and enhanced genetic algorithms (GAs). Analytical studies have also lead to suggest that NK-Landscapes may not be appropriate for testing the performance of GAs. In this work we study the effect of selection, drift, mutation, and recombination on NK-Landscapes for N = 96. We take a model of generational parallel varying mutation GA (GA-SRM) and switch on and off its major components to emphasize each of the four processes mentioned above. We observe that using an appropriate selection pressure and postponing drift make GAs quite robust on NK-Landscapes; different to previous studies, even simple GAs with these two features perform better than a random bit climber (RBC+) for a broad range of classes of problems (K 4). We also observe that the interaction of parallel varying mutation with crossover improves further the reliability of the GA, especially for 12 < K < 32. Contrary to intuition, we find that for small K a mutation only evolutionary algorithm (EA) is very effective and crossover may be omitted; but the relative importance of crossover interacting with varying mutation increases with K performing better than mutation alone (K > 12). This work indicates that NK-Landscapes are useful for testing each one of the major processes involved in a GA and for assessing the overall behavior of a GA on complex non-linear problems. This study also gives valuable guidance to practitioners applying GAs to real world problems of how to configure the GA to achieve better results as the non-linearity and complexity of the problem increases.

General packet radio service (GPRS) uses a two-stage mechanism to allocate uplink radio resource to mobile stations (MSs). In stage-1, the base station (BS) assigns several packet data channels (PDCHs) to an MS. Furthermore, a PDCH may be assigned to multiple MSs. In stage-2, therefore, the BS selects one of the multiplexed MSs in a PDCH to use the radio resource. In this paper, maintaining a load balance between PDCHs in stage-1 is examined and several selection schemes to lower the mis-selection rate in stage-2 are proposed. From our simulation results, the cost deduced from the poor load balancing and selection schemes render a lower system throughput and a non-negligible increase in packet queuing delay. Among the various stage-2 selection policies, round robin with linearly-accumulated adjustment (RRLAA) has the lowest mis-selection rate and outperforms the one without any heuristic by up to 50%.