A hard real-time system is one whose correctness depends not only on the logical result, but also when the results are produced. While many techniques have been proposed for single processor real-time systems, multiprocessor systems have not been studied so extensively. In this paper, we mainly propose two variant (DCTS) by using the Early-Release-Fair (ERfair) and Proportionate-fair (Pfair) model with integral assumptions for identical multi-processor real-time systems. ERfair is a scheduling model for real-time tasks on a multiprocessor system. On the different definitions of distance constraint, we propose two efficient scheduling algorithms designed to probe whether the distance constraints of all ER-fair tasks can be guaranteed. If the distance constraints cannot be guaranteed, then the proposed algorithms gather the unfeasible tasks and inflate them with a reweighting function. The proposed algorithms are linear-time and most suitable for dynamic systems. The experimental results reveal that the proposed algorithms increase significantly the ratio of schedulable task sets.

In this paper, we propose two techniques to solve the nonlinear constrained optimization problem in large scale mesh-interconnected system. The first one is a diagram-method-based decomposition technique which decomposes the large scale system into some small subsystems. The second technique is a projected-Jacobi-based parallel dual-type method which can solve the optimization problems in the decomposed subsystems efficiently. We have used the proposed algorithm to solve numerous examples of large scale constrained optimization problems in power system. The test results show that the proposed algorithm has computational efficiency with respect to the conventional approach of the centralized Newton method and the state-of-the-art Block-Parallel Newton method.

A deep null algorithm for adaptive narrowband beamforming in the presence of array gain errors is proposed. This new algorithm not only preserves the desired signal, but also yields superior performance. Simulations confirm this new approach.

The convergence speed of the conventional adaptive LMS algorithms for time delay estimation (TDE) is highly dependent on the spectral distribution of the desired random source signals of interest, thus the performance of TDE might be degraded, dramatically. To solve this problem, in this letter, a DCT-transform domain constrained adaptive normalized-LMS filtering scheme, referred to as the adaptive constrained DCT-LMS algorithm, is devised for TDE. Computer simulation results verify that the proposed scheme can be used to achieve desired performance, for input random signals with different spectral distributions; it outperforms the unconstrained DCT-LMS and time-domain constrained adaptive LMS algorithms.

The minimization problem of an L2-sensitivity measure subject to L2-norm dynamic-range scaling constraints is formulated for a class of two-dimensional (2-D) state-space digital filters. First, the problem is converted into an unconstrained optimization problem by using linear-algebraic techniques. Next, the unconstrained optimization problem is solved by applying an efficient quasi-Newton algorithm with closed-form formula for gradient evaluation. The coordinate transformation matrix obtained is then used to synthesize the optimal 2-D state-space filter structure that minimizes the L2-sensitivity measure subject to L2-norm dynamic-range scaling constraints. Finally, a numerical example is presented to illustrate the utility of the proposed technique.

Developing embedded parallel image processing applications is usually a very hardware-dependent process, often using the single instruction multiple data (SIMD) paradigm, and requiring deep knowledge of the processors used. Furthermore, the application is tailored to a specific hardware platform, and if the chosen hardware does not meet the requirements, it must be rewritten for a new platform. We have proposed the use of design space exploration [9] to find the most suitable hardware platform for a certain application. This requires a hardware-independent program, and we use algorithmic skeletons [5] to achieve this, while exploiting the data parallelism inherent to low-level image processing. However, since different operations run best on different kinds of processors, we need to exploit task parallelism as well. This paper describes how we exploit task parallelism using an asynchronous remote procedure call (RPC) system, optimized for low-memory and sparsely connected systems such as smart cameras. It uses a futures [16]-like model to present a normal imperative C-interface to the user in which the skeleton calls are implicitly parallelized and pipelined. Simulation provides the task dependency graph and performance numbers for the mapping, which can be done at run time to facilitate data dependent branching. The result is an easy to program, platform independent framework which shields the user from the parallel implementation and mapping of his application, while efficiently utilizing on-chip memory and interconnect bandwidth.

A lexicon is an important linguistic resource needed for both shallow and deep language processing. Currently, there are few machine-readable Thai dictionaries available, and most of them do not satisfy the computational requirements. This paper presents the design of a Thai lexicon named the TCL's Computational Lexicon (TCLLEX) and proposes a method to construct a large-scale Thai lexicon by re-using two existing dictionaries and a large number of texts on the Internet. In addition to morphological, syntactic, semantic case role and logical information in the existing dictionaries, a sort of semantic constraint called selectional preference is automatically acquired by analyzing Thai texts on the web and then added into the lexicon. In the acquisition process of the selectional preferences, the so-called Bayesian Information Criterion (BIC) is applied as the measure in a tree cut model. The experiments are done to verify the feasibility and effectiveness of obtained selection preferences.

Constraint-based software specifications enable run-time monitoring to detect probable risk events and ensure the desired system behavior. SpecTRM-RL is a well-developed constraint-based specification method for computer-controlled systems. However, it is desirable to express constraints in familiar visual models. To provide better visualization and popularity, we developed methods to represent all the SpecTRM-RL constraint types in UML. We have also extended SpecTRM's constraints by adding relational and global constraints, and then expressed them in OCL. Safety verification of these specifications is also proposed. We developed a systematic way to construct fault trees for safety analysis based on UML diagrams. Due to the generality of UML as well as the defensive manner of constraints and fault tree analysis, our approach can be adapted for both general applications and safety-critical applications.

A power and spreading gain allocation strategy is considered for effectively providing data services for mobile users with different levels of priorities in a DS-CDMA system supporting real-time and non-real-time services. Specifically, the uplink in the DS-CDMA system is considered subject to a constraint on total power received at the base station caused by non-real-time data services. The constraint is imposed to meet QoS requirements of real-time services. The priority level of a data user is specified by the weighting factor assigned to the data throughput of the user. Our strategy implements a relative prioritization that affords a trade-off between spectral efficiency and strict prioritization.

A novel technique is proposed for measuring the distributed strain and temperature in a fiber with a very high resolution. This technique makes use of the jagged appearance of Rayleigh backscatter traces from a single-mode fiber measured by using a coherent OTDR with a precisely frequency-controlled light source. Our preliminary experiment indicated the possibility of measuring temperature with a resolution of better than 0.01 and a spatial resolution of one meter. This temperature resolution is two orders of magnitude better than that provided by Brillouin-based distributed sensors.

The protein threading problem with profiles is known to be efficiently solvable using dynamic programming. In this paper, we consider a variant of the protein threading problem with profiles in which constraints on distances between residues are given. We prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (Protein Data Bank) using simulated distance constraints. The results show that constraints are useful to improve the alignment accuracy of the target sequence and the template structure. Moreover, these results also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.

The perfect matched layer (PML) is formulated for the use in the constrained interpolation profile (CIP) method. Numerical results are presented to examine the performance of the proposed formulation of the PML in the case of two-dimensional TM wave. The results show that the proposed methods suppress the reflection effectively in comparison with the natural absorbing boundary condition of the CIP method. We have two methods to formulate the PML, and it is shown that the both methods have equal characteristics.

In this letter we consider topology control and routing problem in wireless networks where equipped with point-to-point wireless links such as directional antennas or free space optics. In point-to-point wireless networks, each node has a limited number of transceivers and hence can communicate with only a limited number of nodes within its transmission range. The selection of the limited number of neighbors is very critical for the network performance. In this letter, we propose a topology control algorithms which consider the topology control and routing of each demand is considered simultaneously. For this, we introduce the degree constraint shortest path problem for finding optimal (shortest) paths in wireless point-to-point networks. Also, we propose two topology control algorithms: minimum hop (MHA) and resource availability ratio (RAR) algorithm. The resource availability ratio algorithm considers not only the available link bandwidth but also the available interfaces between neighbors. By simulation experiments, we compare the performance of each algorithm.

We have proposed a neural network called the Lagrange programming neural network with polarized high-order connections (LPPH) for solving the satisfiability problem (SAT) of propositional calculus. The LPPH has gradient descent dynamics for variables and gradient ascent dynamics for Lagrange multipliers, which represent the weights of the clauses of the SAT. Each weight wr increases according to the degree of unsatisfaction of clause Cr. This causes changes in the energy landscape of the Lagrangian function, on which the values of the variables change in the gradient descent direction. It was proved that the LPPH is not trapped by any point that is not a solution of the SAT. Experimental results showed that the LPPH can find solutions faster than existing methods. In the LPPH dynamics, a function hr(x) calculates the degree of unsatisfaction of clause Cr via multiplication. However, this definition of hr(x) has a disadvantage when the number of literals in a clause is large. In the present paper, we propose a new definition of hr(x) in order to overcome this disadvantage using the "min" operator. In addition, we extend the LPPH to solve the constraint satisfaction problem (CSP). Our neural network can update all neurons simultaneously to solve the CSP. In contrast, conventional discrete methods for solving the CSP must update variables sequentially. This is advantageous for VLSI implementation.

The k-edge-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, kECA-SV-DC, is defined as follows: "Given an undirected multigraph G = (V,E), a specified set of vertices S ⊆V and a function g: V → Z+ ∪{∞}, find a smallest set E' of edges such that (V,E ∪ E') has at least k edge-disjoint paths between any pair of vertices in S and such that, for any v ∈ V, E' includes at most g(v) edges incident to v, where Z+ is the set of nonnegative integers." This paper first shows polynomial time solvability of kECA-SV-DC and then gives a linear time algorithm for 2ECA-SV-DC.

The changes in fiber strain and fiber loss with temperature are quantitatively evaluated for 0.5 mm UV-coated fiber and three kind of fiber-optic access cables, for dropping and indoor wiring, employing 0.5 mm UV-coated fiber. Measurements of the fiber strain and loss increase are conducted using a quasi-heterodyne interferometer method and a photon-counting optical-time-domain-reflectmeter, respectively, at 1.3 and 1.55 µ m. From the strain characteristics, the following observations are made: (a) In the temperature range from -40 to 20 the fiber strain followed the cable strain quite closely, thus maintaining a tight cable structure and (b) from 20 to 80, the fiber exhibited a lower strain than the cable strain. Furthermore, no loss increase due to temperature change was observed for the 0.5-mm diameter coated fiber and the three type of optical cables.

Cooperative transmission among users in multiple access wireless environments is an efficient way to obtain the powerful benefits of multi-antenna systems without the need for physical arrays. Its performance in relay networks were extensively analyzed but most papers only focused on the case of high signal-to-noise ratio (SNR) or loose power constraints. Based on the approximation of total SNR distributions of the propagation paths through relays as the exponential functions, we derive the analytical BER expression in a simple form for general relay networks under strict power restriction. Numerical and simulation results reveal the high accuracy of the distribution estimation as well as the high reliability of the deduced formula, especially at the low SNR.

The 2-vertex-connectivity augmentation problem for a specified set of vertices of a graph with degree constraints, 2VCA-SV-DC, is defined as follows: "Given an undirected graph G = (V,E), a specified set of vertices S ⊆V with |S|3 and a function g:V→Z+∪{∞}, find a smallest set E' of edges such that (V,E ∪E') has at least two internally-disjoint paths between any pair of vertices in S and such that vertex-degree increase of each v ∈V by the addition of E' to G is at most g(v), where Z+ is the set of nonnegative integers." This paper shows a linear time algorithm for 2VCA-SV-DC.

This paper discusses clock skew due to manufacturing variability and environmental change. In clock tree design, transition time constraint is an important design parameter that controls clock skew and power dissipation. In this paper, we evaluate clock skew under several variability models, and demonstrate relationship among clock skew, transition time constraint and power dissipation. Experimental results show that constraint of small transition time reduces clock skew under manufacturing and supply voltage variabilities, whereas there is an optimum constraint value for temperature gradient. Our experiments in a 0.18 µm technology indicate that clock skew is minimized when clock buffer is sized such that the ratio of output and input capacitance is four.

This work proposes a technique to automatically obtain timing constraints for a given timed circuit to operate correctly. A designated set of delay parameters of a circuit are first set to sufficiently large bounds, and verification runs followed by failure analysis are repeated. Each verification run performs timed state space enumeration under the given delay bounds, and produces a failure trace if it exists. The failure trace is analyzed, and sufficient timing constraints to prevent the failure are obtained. Then, the delay bounds are tightened according to the timing constraints by using an ILP (Integer Linear Programming) solver. This process terminates when either some delay bounds under which no failure is detected are found or no new delay bounds to prevent the failures can be obtained. The experimental results using a naive implementation show that the proposed method can efficiently handle asynchronous benchmark circuits and nontrivial GasP circuits.