Scheduling chain combination is the core of chain-based scheduling algorithms, the speed of which determines the overall performance of corresponding scheduling algorithm. However, backtracking is used in general comb...Scheduling chain combination is the core of chain-based scheduling algorithms, the speed of which determines the overall performance of corresponding scheduling algorithm. However, backtracking is used in general combination algorithms to traverse the whole search space which may introduce redundant operations, so performance of the combination algorithm is generally poor. A fast scheduling chain combination algorithm which avoids redundant operations by skipping “incompatible” steps of scheduling chains and using a stack to remember the scheduling state is presented in this paper to overcome the problem. Experimental results showed that it can improve the performance of scheduling algorithms by up to 15 times. By further omitting unnecessary operations, a fast algorithm of minimum combination length prediction is developed, which can improve the speed by up to 10 times.展开更多
On board processing(OBP) satellite systems have obtained more and more attentions in recent years because of their high efficiency and performance.However,the OBP transponders are very sensitive to the high energy par...On board processing(OBP) satellite systems have obtained more and more attentions in recent years because of their high efficiency and performance.However,the OBP transponders are very sensitive to the high energy particles in the space radiation environments.Single event upset(SEU)is one of the major radiation effects,which influences the satellite reliability greatly.Triple modular redundancy(TMR) is a classic and efficient method to mask SEUs.However,TMR uses three identical modules and a comparison logic,the circuit size becomes unacceptable,especially in the resource limited environments such as OBP systems.Considering that,a new SEU-tolerant method based on residue code and high-level synthesis(HLS) is proposed,and the new method is applied to FIR filters,which are typical structures in the OBP systems.The simulation results show that,for an applicable HLS scheduling scheme,area reduction can be reduced by 48.26%compared to TMR,while fault missing rate is 0.15%.展开更多
This paper intends to provide theoretical basis for matching design of hydraulic load simulator （HLS） with aerocraft actuator in hardware-in-loop test, which is expected to help actuator designers overcome the obsta...This paper intends to provide theoretical basis for matching design of hydraulic load simulator （HLS） with aerocraft actuator in hardware-in-loop test, which is expected to help actuator designers overcome the obstacles in putting forward appropriate requirements of HLS. Traditional research overemphasizes the optimization of parameters and methods for HLS controllers. It lacks deliberation because experimental results and project experiences indicate different ultimate performance of a specific HLS. When the actuator paired with this HLS is replaced, the dynamic response and tracing precision of this HLS also change, and sometimes the whole system goes so far as to lose control. Based on the influence analysis of the preceding phenomena, a theory about matching design of aerocraft actuator with HLS is presented, together with two paired new concepts of ＂Standard Actuator＂ and ＂Standard HLS＂. Further research leads to seven important conclusions of matching design, which suggest that appropriate stiffness and output torque of HLS should be carefully designed and chosen for an actuator. Simulation results strongly support that the proposed principle of matching design can be anticipated to be one of the design criteria for HLS, and successfully used to explain experimental phenomena and project experiences.展开更多
We proposed a novel solution schema called the Hierarchical Labeling Schema （HLS） to answer reachability queries in directed graphs. Different from many existing approaches that focus on static directed acyclic grap...We proposed a novel solution schema called the Hierarchical Labeling Schema （HLS） to answer reachability queries in directed graphs. Different from many existing approaches that focus on static directed acyclic graphs （DAGs）, our schema focuses on directed cyclic graphs （DCGs） where vertices or arcs could be added to a graph incrementally. Unlike many of the traditional approaches, HLS does not require the graph to be acyclic in constructing its index. Therefore, it could, in fact, be applied to both DAGs and DCGs. When vertices or arcs are added to a graph, the HLS is capable of updating the index incrementally instead of re-computing the index from the scratch each time, making it more efficient than many other approaches in the practice. The basic idea of HLS is to create a tree for each vertex in a graph and link the trees together so that whenever two vertices are given, we can immediately know whether there is a path between them by referring to the appropriate trees. We conducted extensive experiments on both real-world datasets and synthesized datasets. We compared the performance of HLS, in terms of index construction time, query processing time and space consumption, with two state-of-the-art methodologies, the path-tree method and the 3-hop method. We also conducted simulations to model the situation when a graph is updated incrementally. The performance comparison of different algorithms against HLS on static graphs has also been studied. Our results show that HLS is highly competitive in the practice and is particularly useful in the cases where the graphs are updated frequently.展开更多
Register allocation in high-level circuit synthesis is important not only for reducing area, delay, and power overheads, but also for improving the testability of the synthesized circuits. This paper presents an impro...Register allocation in high-level circuit synthesis is important not only for reducing area, delay, and power overheads, but also for improving the testability of the synthesized circuits. This paper presents an improved register allocation algorithm that improves the testability called weighted graph-based balanced register allocation for high-level circuit synthesis. The controllability and observability of the registers and the self-loop elimination are analyzed to form a weighted conflict graph, where the weight of the edge between two nodes denotes the tendency of the two variables to share the same register. Then the modified desaturation algorithm is used to dynamically modify the weights to obtain a final balanced register allocation which improves the testability of the synthesized circuits a higher fault coverage than other algorithms with Tests on some benchmarks show that the algorithm gives less area overhead and even less time delay.展开更多
基金Project (No. Y105355) supported by the Natural Science Foundationof Zhejiang Province, China
文摘Scheduling chain combination is the core of chain-based scheduling algorithms, the speed of which determines the overall performance of corresponding scheduling algorithm. However, backtracking is used in general combination algorithms to traverse the whole search space which may introduce redundant operations, so performance of the combination algorithm is generally poor. A fast scheduling chain combination algorithm which avoids redundant operations by skipping “incompatible” steps of scheduling chains and using a stack to remember the scheduling state is presented in this paper to overcome the problem. Experimental results showed that it can improve the performance of scheduling algorithms by up to 15 times. By further omitting unnecessary operations, a fast algorithm of minimum combination length prediction is developed, which can improve the speed by up to 10 times.
基金Supported by the National S&T Major Project(No.2011ZX03003-003-01,2011ZX03004-004)the National Basic Research Program of China(No.2012CB316002)
文摘On board processing(OBP) satellite systems have obtained more and more attentions in recent years because of their high efficiency and performance.However,the OBP transponders are very sensitive to the high energy particles in the space radiation environments.Single event upset(SEU)is one of the major radiation effects,which influences the satellite reliability greatly.Triple modular redundancy(TMR) is a classic and efficient method to mask SEUs.However,TMR uses three identical modules and a comparison logic,the circuit size becomes unacceptable,especially in the resource limited environments such as OBP systems.Considering that,a new SEU-tolerant method based on residue code and high-level synthesis(HLS) is proposed,and the new method is applied to FIR filters,which are typical structures in the OBP systems.The simulation results show that,for an applicable HLS scheduling scheme,area reduction can be reduced by 48.26%compared to TMR,while fault missing rate is 0.15%.
基金the Aviation Science Foundation (No. 20110951009) of ChinaNational Nature Science Foundation for Distinguished Young Scholars ( No. 50825502 ) of China for the financial support
文摘This paper intends to provide theoretical basis for matching design of hydraulic load simulator （HLS） with aerocraft actuator in hardware-in-loop test, which is expected to help actuator designers overcome the obstacles in putting forward appropriate requirements of HLS. Traditional research overemphasizes the optimization of parameters and methods for HLS controllers. It lacks deliberation because experimental results and project experiences indicate different ultimate performance of a specific HLS. When the actuator paired with this HLS is replaced, the dynamic response and tracing precision of this HLS also change, and sometimes the whole system goes so far as to lose control. Based on the influence analysis of the preceding phenomena, a theory about matching design of aerocraft actuator with HLS is presented, together with two paired new concepts of ＂Standard Actuator＂ and ＂Standard HLS＂. Further research leads to seven important conclusions of matching design, which suggest that appropriate stiffness and output torque of HLS should be carefully designed and chosen for an actuator. Simulation results strongly support that the proposed principle of matching design can be anticipated to be one of the design criteria for HLS, and successfully used to explain experimental phenomena and project experiences.
文摘We proposed a novel solution schema called the Hierarchical Labeling Schema （HLS） to answer reachability queries in directed graphs. Different from many existing approaches that focus on static directed acyclic graphs （DAGs）, our schema focuses on directed cyclic graphs （DCGs） where vertices or arcs could be added to a graph incrementally. Unlike many of the traditional approaches, HLS does not require the graph to be acyclic in constructing its index. Therefore, it could, in fact, be applied to both DAGs and DCGs. When vertices or arcs are added to a graph, the HLS is capable of updating the index incrementally instead of re-computing the index from the scratch each time, making it more efficient than many other approaches in the practice. The basic idea of HLS is to create a tree for each vertex in a graph and link the trees together so that whenever two vertices are given, we can immediately know whether there is a path between them by referring to the appropriate trees. We conducted extensive experiments on both real-world datasets and synthesized datasets. We compared the performance of HLS, in terms of index construction time, query processing time and space consumption, with two state-of-the-art methodologies, the path-tree method and the 3-hop method. We also conducted simulations to model the situation when a graph is updated incrementally. The performance comparison of different algorithms against HLS on static graphs has also been studied. Our results show that HLS is highly competitive in the practice and is particularly useful in the cases where the graphs are updated frequently.
基金Supported by the National Key Basic Research and Development(973) Program of China (No. 2005CB321604)the National Natural Science Foundation of China (No. 60633060)
文摘Register allocation in high-level circuit synthesis is important not only for reducing area, delay, and power overheads, but also for improving the testability of the synthesized circuits. This paper presents an improved register allocation algorithm that improves the testability called weighted graph-based balanced register allocation for high-level circuit synthesis. The controllability and observability of the registers and the self-loop elimination are analyzed to form a weighted conflict graph, where the weight of the edge between two nodes denotes the tendency of the two variables to share the same register. Then the modified desaturation algorithm is used to dynamically modify the weights to obtain a final balanced register allocation which improves the testability of the synthesized circuits a higher fault coverage than other algorithms with Tests on some benchmarks show that the algorithm gives less area overhead and even less time delay.
