The method of transforming a ladder diagram (LD) and an instruction list (IL) of PLC (Programmable Logic Controller) to each other is investigated in this paper. Firstly, ladder-step is adopted on transforming LD into...
详细信息
ISBN:
(纸本)9783037853849
The method of transforming a ladder diagram (LD) and an instruction list (IL) of PLC (Programmable Logic Controller) to each other is investigated in this paper. Firstly, ladder-step is adopted on transforming LD into IL. Ladder-step is divided series or parallel by using recursive algorithm, and then complicated ladder-step can be divided into several simple ladder-steps which can be converted to IL easily. When obtaining simple ladder-steps' IL, combining them together to get final IL program of complicated LD program. Secondly, on transforming IL into LD, stack algorithm contributes a lot. Scanning IL to generate LD of each instruction block, and then pushing them into stack. Combine LDs in the stack by operating instruction, and then IL is transformed into LD successfully. Finally, in the last part of this paper, we show our PLC software and lower position machine. In addition, this transforming algorithm has already applied in PLC software successfully.
Current graphics processing units (GPUs) utilize the single instruction multiple thread (SIMT) execution model. With SIMT, a group of logical threads executes such that all threads in the group execute a single common...
详细信息
ISBN:
(纸本)9781467355872
Current graphics processing units (GPUs) utilize the single instruction multiple thread (SIMT) execution model. With SIMT, a group of logical threads executes such that all threads in the group execute a single common instruction on a particular cycle. To enable control flow to diverge within the group of threads, GPUs partially serialize execution and follow a single control flow path at a time. The execution of the threads in the group that are not on the current path is masked. Most current GPUs rely on a hardware reconvergence stack to track the multiple concurrent paths and to choose a single path for execution. Control flow paths are pushed onto the stack when they diverge and are popped off of the stack to enable threads to reconverge and keep lane utilization high. The stack algorithm guarantees optimal reconvergence for applications with structured control flow as it traverses the structured control-flow tree depth first. The downside of using the reconvergence stack is that only a single path is followed, which does not maximize available parallelism, degrading performance in some cases. We propose a change to the stack hardware in which the execution of two different paths can be interleaved. While this is a fundamental change to the stack concept, we show how dual-path execution can be implemented with only modest changes to current hardware and that parallelism is increased without sacrificing optimal (structured) control-flow reconvergence. We perform a detailed evaluation of a set of benchmarks with divergent control flow and demonstrate that the dual-path stack architecture is much more robust compared to previous approaches for increasing path parallelism. Dual-path execution either matches the performance of the baseline single-path stack architecture or outperforms single-path execution by 14.9% on average and by over 30% in some cases.
In this paper, we consider the design of multi-stream demodulators for multiple-input multiple-output (MIMO) systems. Our proposed MIMO demodulator is based on the stack tree-search strategy and provides soft-outputs ...
详细信息
In this paper, we consider the design of multi-stream demodulators for multiple-input multiple-output (MIMO) systems. Our proposed MIMO demodulator is based on the stack tree-search strategy and provides soft-outputs in the form of exact max-log log-likelihood ratios (max-log LLRs). We prove that our proposed demodulator is optimally efficient in that it visits the least number of nodes among all optimal demodulators in a class of tree-search-based demodulators. We conduct a comprehensive complexity analysis of such optimally efficient demodulators. We also identify key parameters associated with our proposed demodulator that can be controlled to realize near max-log performance with substantially reduced complexity, as demonstrated via simulations.
In this paper, we propose a computationally efficient decoding algorithm for space-time trellis codes in slow Rayleigh fading channels. The proposed scheme is based on a stack algorithm with two key ideas: (i) a varia...
详细信息
In this paper, we propose a computationally efficient decoding algorithm for space-time trellis codes in slow Rayleigh fading channels. The proposed scheme is based on a stack algorithm with two key ideas: (i) a variable stack size depending upon the signal-to-noise ratio to avoid the exhaustive search of paths and (ii) a normalized metric, which is defined as each cumulative path metric divided by its own length in the stack, to provide an appropriate comparison of the paths with different lengths. Simulation results demonstrate that the proposed algorithm achieves near-ML performance with significant reduction in complexity, compared with the conventional Viterbi algorithm.
We propose complexity efficient tree search approaches to detection and estimation problems, and we consider both communication and target tracking applications in this regard. We formulate the problems of interest us...
详细信息
We propose complexity efficient tree search approaches to detection and estimation problems, and we consider both communication and target tracking applications in this regard. We formulate the problems of interest using a dynamic state space model, where we seek to estimate the system state from sensor observations. The proposed tree search approach initializes a search tree from a given initially estimated system state. With each new observation, the algorithm expands the search tree to find the best possible system state. The paths through the search tree correspond to sequences of system states. They are evaluated by their associated path metrics, which are proportional to the posterior probability of the system state. The stack algorithm and the M-algorithm, two tree search approaches that were originally used for decoding convolutionally-encoded sequences, are applied to reduce the complexity of the tree search.@pqdt@break@In wireless communication applications, we have considered blind channel equalization of time-varying channels and modulation classification of an unknown received signal. For both applications, tree search approaches are implemented to find the transmitted information sequence that maximizes the posterior probability distribution function of the system state. For blind channel equalization of time-varying channels, an exponentially decaying window, matched to the variation rate of the channel, is implemented in the path metric calculation to successfully equalize an unknown time-varying channel. For modulation classification of challenging high-density QAM (Quadrature Amplitude Modulation) schemes, the statistical properties of the mean square error are derived analytically and compared with those of the estimated sequence to identify the modulation scheme of the received signal. The proposed tree-search approaches provide superior performance in comparison with other competitive approaches.@pqdt@break@In target tracking applications, the p
stack algorithm (SA) has been proved to be the most efficient one among the existing sphere decoding algorithms, although it needs a large amount of time-consuming comparisons. In this paper, a pruning stack algorithm...
详细信息
ISBN:
(纸本)9781424414482
stack algorithm (SA) has been proved to be the most efficient one among the existing sphere decoding algorithms, although it needs a large amount of time-consuming comparisons. In this paper, a pruning stack algorithm (PSA) is proposed to decrease the size of the border node list in SA by. statistical pruning. With a proper configuration, a good tradeoff is achieved between the performance and complexity. For high order modulations, PSA is able to reduce the number of comparisons by at least 30% as compared to SA without much penalty of the performance.
In this paper, we consider a low-complexity detection technique referred to as a reduced dimension maximum-likelihood search (RD-MLS). RD-MLS is based on a partitioned search which approximates the maximum-likelihood ...
详细信息
In this paper, we consider a low-complexity detection technique referred to as a reduced dimension maximum-likelihood search (RD-MLS). RD-MLS is based on a partitioned search which approximates the maximum-likelihood (ML) estimate of symbols by searching a partitioned symbol vector space rather than that spanned by the whole symbol vector. The inevitable performance loss due to a reduction in the search space is compensated by 1) the use of a list tree search, which is an extension of a single best searching algorithm called sphere decoding, and 2) the recomputation of a set of weak symbols, i. e., those ignored in the reduced dimension search, for each strong symbol candidate found during the list tree search. Through simulations on M-quadrature amplitude modulation (QAM) transmission in frequency nonselective multi-input-multioutput (MIMO) channels, we demonstrate that the RD-MLS algorithm shows near constant complexity over a wide range of bit error rate (BER) (10(-1) similar to 10(-4)), while limiting performance loss to within 1 dB from ML detection.
We propose a family of list-based soft demodulators for multiple-input-multiple-output (MIMO) communication systems based on a multistack algorithm for traversing the tree structure that is inherent in the MIMO demodu...
详细信息
We propose a family of list-based soft demodulators for multiple-input-multiple-output (MIMO) communication systems based on a multistack algorithm for traversing the tree structure that is inherent in the MIMO demodulation problem. The existing stack algorithm for MIMO soft demodulation stores a single stack of visited nodes in the tree and expands the stack using the "best-first" principle. In the proposed multistack algorithm, the single stack is partitioned into a stack for each level of the tree, and the algorithm proceeds by performing one best-first search step in each of these stacks in the natural ordering of the tree. By assigning appropriate priorities to the level at which this "best-first search per level" processing restarts once a leaf node has been obtained, the proposed demodulators can achieve tradeoffs between performance and complexity that dominate those of several existing methods, including the stack algorithm, in the low-complexity region.
A ray cast algorithm utilizing a hierarchical acceleration structure needs to perform a tree traversal in the hierarchy. In its basic form, executing the traversal requires a stack that holds the nodes that are still ...
详细信息
ISBN:
(纸本)9781617827242
A ray cast algorithm utilizing a hierarchical acceleration structure needs to perform a tree traversal in the hierarchy. In its basic form, executing the traversal requires a stack that holds the nodes that are still to be processed. In some cases, such a stack can be prohibitively expensive to maintain or access, due to storage or memory bandwidth limitations. The stack can, however, be eliminated or replaced with a fixed-size buffer using so-called stackless or short stack algorithms. These require that the traversal can be restarted from root so that the already processed part of the tree is not entered again. For kd-tree ray casts, this is accomplished easily by ray shortening, but the approach does not extend to other kinds of hierarchies such as BVHs. In this paper, we introduce restart trail, a simple algorithmic method that makes restarts possible regardless of the type of hierarchy by storing one bit of data per level. This enables stackless and short stack traversal for BVH ray casts, where using a full stack or constraining the traversal order have so far been the only options.
Hardware implementations of tree search-based multiple-input multiple-output (MIMO) detection often have limited performance due to large memory requirement or high computational complexity of sophisticated MIMO detec...
详细信息
Hardware implementations of tree search-based multiple-input multiple-output (MIMO) detection often have limited performance due to large memory requirement or high computational complexity of sophisticated MIMO detection algorithms. In this paper, we propose new tree search-based detection algorithms that achieve maximum-likelihood (ML) performance under any given memory constraints and with reduced computational complexity. To this end, we make two main contributions. First, we propose a memory-constrained tree search (MCTS) algorithm that bridges the gap between the sphere decoding (SD) and stack algorithms. Our MCTS algorithm dynamically adapts to any pre-specified memory constraint and offers a graceful tradeoff between computational complexity and memory requirement while maintaining the ML performance. When the memory size is set as the minimum, our MCTS algorithm is similar to the SD algorithm. As the memory size increases, the average computational complexity of our MCTS algorithm decreases. When the memory size becomes large, our MCTS algorithm is similar to the stack algorithm, having similar average computational complexity but requiring significantly less memory. To further reduce the computational complexity of tree search-based ML detection algorithms, we propose novel ordering schemes that can be easily embedded in the QR decomposition and take into account both the channel matrix and the received signal (noise);simulation results show that our ordering schemes lead to reduced average computational complexity for the SD and MCTS algorithms, and the reduction is significant at low to medium signal-to-noise ratio region.
暂无评论