Efficient and scalable quicksort on a linear array with a reconfigurable pipelined bus system

Based on the current fiber optic technology, a new computational model, called a linear array with a reconfigurable pipelined abus system (LARPBS), is proposed in this paper. A parallel quicksort algorithm is implemented on the model, and its time complexity is analyzed. For a set of N numbers, the quicksort algorithm reported in this paper runs in O(log₂ N) average time on a linear array with a reconfigurable pipelined bus system of size N. If the number of processors available is reduced to P, where P < N, the algorithm runs in O((N/P) log₂ N) average time and is still scalable. Besides proposing a new algorithm on the model, some basic data movement operations involved in the algorithm are discussed. We believe that these operations can be used to design other parallel algorithms on the same model. Future research in this area is also identified in this paper.     

Parallel algorithms for solving the satisfaction problem of functional and multivalued data dependencies

Parallel algorithms for solving the satisfaction problem of non-trivial functional and multivalued data dependencies (FDs and MVDs) in a relation of N tuples by M processors are developed in this paper. Algorithms performing, in a parallel manner, batch or interactive checking of these data dependencies are also discussed. The M processors are organized as a linear systolic array. The time complexities of the first two algorithms for solving the FD satisfaction problem under M N are both O(N), and that of Algorithm (3) or (4) for solving the FD or MVD satisfaction problem under N M is O(N²/M). The latter complexity reduced to O(N) if N = M and is at least not worse than O(N log N) if N = M (N/log N).     

Poly(acrylamide) derivatives for QCM-based HCl gas sensor applications

Quartz resonators coated with three kinds of poly(acrylamide) derivatives were studied for simply but accurately detecting HCl gas in air. The exposure of the resonator to HCl gas reversibly decreased the oscillation frequencies. The sensitivity, response time, and reversibility were found to depend on the structure of the amide group. Among the polymers used, poly(N,N-dimethylacrylamide) (PDMAA) showed the most relevant data for the HCl sensor. The HCl sensitivity obtained for PDMAA was ca. 250 ppb/Hz. On the other hand, the irreversible response toward NO₂ gas was considerably high, and great interference was also produced by changes in the test gas humidity.     

Distributed selectsort sorting algorithms on broadcast communication networks

In this paper, a distributed selectsort algorithm and a parameterized selectsort algorithm are presented to be applied on distributed systems for cases when N P where N is the number of elements to be sorted and P is the number of processors in the system. The distributed system considered in this paper uses a broadcasting channel for communication between processors. We show that the number of messages required for the parameterized selectsort algorithm is independent of N and is of complexity O(P), which is optimal in a distributed system with P processors. Furthermore, the amount of communication required in terms of elements is N + O(P³) and the computation time complexity is O((N/P)lgN + P²lg(N/P)). Hence, when N P³, the computation time complexity is O((N/P)lgN), which is optimal using P processors. In addition, this parameterized algorithm provides us with a parameter K such that by choosing the value of K allows us to trade among processing requirement, memory requirement, and communication requirement. It is shown that this parameterized algorithm can reduce the communication requirements significantly while only slightly increasing the computation requirements.     

Heaps and heapsort on secondary storage

A heap structure designed for secondary storage is suggested that tries to make the best use of the available buffer space in primary memory. The heap is a complete multi-way tree, with multi-page blocks of records as nodes, satisfying a generalized heap property. A special feature of the tree is that the nodes may be partially filled, as in B-trees. The structure is complemented with priority-queue operations insert and delete-max. When handling a sequence of S operations, the number of page transfers performed is shown to be O(∑_{i = 1}^S(1/P) log_(M/P)(N_i/P)), where P denotes the number of records fitting into a page, M the capacity of the buffer space in records, and N_i, the number of records in the heap prior to the ith operation (assuming P 1 and S> M c · P, where c is a small positive constant). The number of comparisons required when handling the sequence is O(∑_{i = 1}^S log₂ N_i). Using the suggested data structure we obtain an optimal external heapsort that performs O((N/P) log_(M/P)(N/P)) page transfers and O(N log₂ N) comparisons in the worst case when sorting N records.     

A simple approximation for the Erlang loss function

In this paper we present a simple non-iterative computational procedure for approximating the Erlang loss function B(N, ). It is applicable to the practical range 10⁻⁵<B(N, )<10⁻¹ and gives results that are within 10% of the exact values. The formula can be computed on a pocket calculator in constant time and could be used to approximately compute B(N, ) for systems of practically any size.     

Efficient algorithms for computing two nearest-neighbor problems on a rap

This paper makes an improvement of computing two nearest-neighbor problems of images on a reconfigurable array of processors (RAP) by increasing the bus width between processors. Based on a base-n system, a constant time algorithm is first presented for computing the maximum/minimum of N log N-bit unsigned integers on a RAP using N processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Then, two basic operations such as image component labeling and border following are also derived from it. Finally, these algorithms are used to design two constant time algorithms for the nearest neighbor black pixel and the nearest neighbor component problems on an N^1/2 × N^1/2 image using N^1/2 × N^1/2 processors each with N^1/c-bit bus width, where c is a constant and c ≥ 1. Another contribution of this paper is that the execution time of the proposed algorithms is tunable by the bus width.     

A fibre-optic oxygen sensor based on contact charge-transfer absorption

A fibre-optic oxygen (O₂) sensor monitoring at a wavelength of 400 nm has been successfully developed for the determination of gaseous O₂. Its working principle is based on the contact charge-transfer absorption of N,N-dimethyl-p-toluidine and O₂. The response to changes in O₂ concentrations is reversible and in good agreement with the Beer-Lambert law. The response and recovery times are 12 and 26 min, respectively. The sensor can detect a wide range of O₂ concentrations, ranging from 4.3 to 100% O₂. The precision is 1.45% (n=5) in a gas mixture of 95% O₂ in N₂ and the limit of detection is 4.3% O₂ (3σ_b). The sensor is stable with a 0.53% change in sensitivity per hour. There is a 0.25% °C⁻¹ decrease of the sensitivity of the sensor to O₂ in the range 20–34°C. Water vapour and nitrogen dioxide interfere slightly, whereas hydrogen sulphide and hydrogen chloride have moderate interference on the sensor. However, chlorine and sulphur dioxide seriously interfere with the sensor.     

Algorithm for converting a forest of quadtrees to a binary array

An algorithm for reconstructing a binary array of size N sx N from its forest of quadtree representation is presented. The algorithm traverses each tree of the forest in preorder and maps each ‘black’ node into the spatial domain. The time complexity in mapping is O(log N × B_n + B_p), where B_n is the number of black nodes in the forest and B_p is the number of black pixels in the N × N array. The algorithm has been implemented on an Apple II.     

积累N次主动变换的传导知识挖掘

针对前N次可拓变换未引起与之相关的信息元发生传导变换,而N+1次主动变换才能引起与之相关的信息元发生传导变换的实际问题,运用可拓变换、传导效应等,并通过给出信息元某特征对于目标特征灵敏度的概念,深入挖掘此类可拓变换及其传导变换的传导知识。通过对某型导弹武器系统定型过程中的试验数据进行分析,表明该方法是对已有传导知识数据挖掘理论的完善和补充,使传导知识挖掘的理论更加丰富、全面。     

基于无线信道状态信息的跌倒无源监测方法

针对传统基于视频或传感器的跌倒检测方法中环境依赖、空间受限等问题，提出了一种基于无线信道状态信息的跌倒无源检测方法Fallsense。该方法利用普适、低成本的商用WiFi设备，首先采集无线信道状态数据并对数据进行预处理，然后设计动作—信号分析模型，建立轻量级动态模板匹配算法以从时序信道数据中实时检测出承载真实跌倒事件的相关片段。大量实际环境下的实验表明，Fallsense可以实现较高的准确率以及较低的误报率，准确率达到95%，误报率为2.44%。与经典WiFall系统相比，Fallsense将时间复杂度从WiFall的O（mN log N）降低到O（N）（N是样本数，m是特征数），且准确率提高了2.69%，误报率下降了4.66%。实验结果表明，所提方法是一种快速高效的无源跌倒检测方法。     

Nonlinear finite element for modeling reinforced concrete columns in three-dimensional dynamic analysis

A new finite element is proposed for slender, flexure-dominated reinforced concrete columns subjected to cyclic biaxial bending with axial load, and its implementation into a program for the nonlinear static or dynamic analysis of structures in three-dimensions, is described. The element belongs to the class of distributed inelasticity discrete models for the nonlinear dynamic response analysis of frame structures to earthquake ground motions. The element tangent flexibility matrix is constructed at each time step by Gauss-Lobatto integration of the section tangent flexibility matrix along the member length. The tangent flexibility matrix of the cross-section relates the increment of the vector of the three normal stress resultants N, M_y, M_z, to the vector increment of the section deformation measures. ε_o, _y, _z, and is constructed on the basis of the bounding surface of the cross-section, which is defined as the locus of points in the space of the normalized N, M_y, M_z, which correspond to ultimate strength. The bounding surface concept enables the model to produce realistic predictions for the nonlinear response of the cross-section to any arbitrary loading path in the space N-M_y-M_z.The bounding surface is introduced and utilized in a very flexible manner, enabling a variety of cross-sectional shapes to be treated in a unified way. As this flexibility is at the expense of computational simplicity and memory size requirements, emphasis is placed on algorithmic techniques to facilitate numerical implementation and to increase computational efficiency.     

Reduced parameter set descriptions for system and event identification

The operation of a machine generates signatures that carry information about its physical condition and operating parameters. In the case of vibration signatures, these signatures may be so complicated that system identification procedures may converge very slowly, if at all. This is due to the large number of physical degrees of freedom which the system has, which translates into a large number of parameters needed to describe the signal. Our research has focused on ways to reduce the required parameter set to that quick and accurate estimates of the source event and the structural signal path can be made.

We shall discuss two procedures which we have used for achieving these aims. Our examples are drawn from studies of combustion pressure in a diesel engine. The available signal is the casing vibration of the engine, due to combustion onset in a cylinder. The signal is smoothed by windowing the cepstrum, which reduces the number of parameters needed to describe it to N. Once smoothed, there are two ways of separating the contributions from the combustion event itself and the structural path.

The first method is Kalman filtering, which describes the “system” by an adjustable impulse response illustrated by m parameters. The input event is estimated by a small number of N-m parameters. The optimization continues to provide a best estimate of the input and system response. Without the cepstral smoothing that precedes this step however, it is essentially impossible to achieve this optimization.

The second method uses a functional expansion to describe the cepstra of the event itself and the transmission path. The functions are Hermite polynomials, which combined with a Gaussian window are called Hermite functions, and have very useful properties. Using this procedure, we want to determine the coefficients in the series expansion for the event and the system cepstra, and these become the unknown parameters to be determined.

The procedures described here have application to diagnostic monitoring of machines and structures, to security systems, and to noise control. Some examples of prospective applications will be described.     

Reducing partition skew on MapReduce: an incremental allocation approach

MapReduce, a parallel computational model, has been widely used in processing big data in a distributed cluster. Consisting of alternate map and reduce phases, MapReduce has to shuffle the intermediate data generated by mappers to reducers. The key challenge of ensuring balanced workload on MapReduce is to reduce partition skew among reducers without detailed distribution information on mapped data. In this paper, we propose an incremental data allocation approach to reduce partition skew among reducers on MapReduce. The proposed approach divides mapped data into many micro-partitions and gradually gathers the statistics on their sizes in the process of mapping. The micropartitions are then incrementally allocated to reducers in multiple rounds. We propose to execute incremental allocation in two steps, micro-partition scheduling and micro-partition allocation. We propose a Markov decision process (MDP) model to optimize the problem of multiple-round micropartition scheduling for allocation commitment. We present an optimal solution with the time complexity of O(K · N²), in which K represents the number of allocation rounds and N represents the number of micro-partitions. Alternatively, we also present a greedy but more efficient algorithm with the time complexity of O(K · N ln N). Then, we propose a minmax programming model to handle the allocation mapping between micro-partitions and reducers, and present an effective heuristic solution due to its NP-completeness. Finally, we have implemented the proposed approach on Hadoop, an open-source MapReduce platform, and empirically evaluated its performance. Our extensive experiments show that compared with the state-of-the-art approaches, the proposed approach achieves considerably better data load balance among reducers as well as overall better parallel performance.     

Parallel merging: algorithm and implementation results

An efficient parallel algorithm for merging two sorted lists is presented. The algorithm is based on a novel partitioning algorithm that splits the two lists among the processors, in a way that ensures load balance during the merge. The partitioning algorithm can itself be efficiently parallelized, allowing the solution to scale with increased numbers of processors. A shared memory multiprocessor is assumed. The time complexity for partitioning and merging is O(N/p + log N), where p is the number of processors and N is the total number of elements in the two lists. Implementation results on a twenty node Sequent Symmetry multiprocessor are also presented.     

Sensor scheduling in continuous time

Let N be the number of available sensor sources. Noisy observations of an underlying state process are available for these N sources. We consider the continuous time sensor scheduling problem in which N₁ of these N sources are to be chosen to collect data at each time point. This sensor scheduling problem (with switching costs and switching constraints) is formulated as a constrained optimal control problem. In this framework, the controls represent the sensors that are chosen at a particular time. Thus, the control variables are constrained to take values in a discrete set, and switchings between sensors can occur in continuous time. By incorporating recent results on discrete valued optimal control, we show that this problem can be transformed into an equivalent continuous optimal control problem. In this way, we obtain the sensor scheduling policy as well as the associated switching times.     

Closed Bernoulli Production Lines: Analysis, Continuous Improvement, and Leanness

In closed production lines, each part is placed on a carrier at the input of the first machine and is removed from the carrier at the output of the last machine. The first machine is starved if no carriers are available, and the last machine is blocked if the empty carrier buffer is full. The number of carriers in the system is S and the capacity of the empty carrier buffer is N ₀. Under the assumption that the machines obey the Bernoulli reliability model, this paper provides methods for determining if a pair (N ₀, S) impedes the open line performance and, if it does, develops techniques for improvement with respect to S and N ₀. In addition, bottlenecks in closed lines are discussed, and an approach to selecting the smallest N ₀ and S, which result in no impediment, is described.     

Numerical inverse isoparametric mapping in remeshing and nodal quantity contouring

In finite element analysis, isoparametric mapping defined as [(ξ, η) → (x, y): X = N_iξ_i] is widely used. It is a one-to-one mapping and its construction is especially elegant for elements of a variable number of nodes showing its versatile applicability to model curved boundaries. In certain analyses, such as remeshing in dynamic analyses or contouring and others, the inverse of this mapping is inevitably valuable, but its determination is not so straightforward. To avoid solving a system of nonlinear equations, generally an iterative technique of order N² in a two-dimensional mesh is often resorted to. In the paper, this technique is improved by systematically bisecting along a predefined line that reduces the iterations to only order N. Its applications in remeshing and nodal quantity contouring are demonstrated and a possible extension for stress contouring is also discussed. The FORTRAN subroutines for the technique proposed are also given.     

Automatic rotational symmetry determination for shape analysis

The determination of the rotational symmetry of a shape is useful for object recognition and shape analysis in computer vision applications. In this paper, a simple, but effective, algorithm to analyse the rotational symmetry of a given closed-curve shape S is proposed. A circle C with the centroid of S as the circle center and the average radius of S as the circle radius is superimposed on S, resulting in the intersection of C and S at a set of points. By theoretical analysis, the relationship between the order N_s of the rotational symmetry of S and the number of intersection points between C and S is established. All the possible values for N_s are determined. And finally N_s is determined by evaluating the similarity between S and its rotated versions. In the proposed algorithm, only simple pixel operations and second-order moment function computation are involved. Several problems caused by the use of discrete image coordinates are analysed and solved for correct decision-making in the algorithm. Good experimental results are also included.