Most view articles
2015, 37(1):14-20.
DOI: 10.11887/j.cn.201501003
Abstract:
To reduce remote cache transfer latency and improve the performance of shared memory systems, a new last-write-touch prediction scheme that exploits the inherent write characteristics of a program is proposed and a directory protocol to support the scheme is adapted. By predicting a last-write-touch and self downgrading a cache block in advance, a processor can get the data from the memory directly and one network hop can be saved for a remote cache access. Compared with the existing instruction-based prediction technique, much storage overhead can be reduced. Experimental results show that it can achieve an average prediction accuracy of 83.1%, leading to improvements up to average 8.57% on the final application performance. Moreover, compared with the instruction-based prediction scheme, the scheme can reduce the storage overheads of the history table by 69% and the storage overheads of the signature table by 36%.
To reduce remote cache transfer latency and improve the performance of shared memory systems, a new last-write-touch prediction scheme that exploits the inherent write characteristics of a program is proposed and a directory protocol to support the scheme is adapted. By predicting a last-write-touch and self downgrading a cache block in advance, a processor can get the data from the memory directly and one network hop can be saved for a remote cache access. Compared with the existing instruction-based prediction technique, much storage overhead can be reduced. Experimental results show that it can achieve an average prediction accuracy of 83.1%, leading to improvements up to average 8.57% on the final application performance. Moreover, compared with the instruction-based prediction scheme, the scheme can reduce the storage overheads of the history table by 69% and the storage overheads of the signature table by 36%.
2017, 39(5):6-13.
DOI: 10.11887/j.cn.201705002
Abstract:
For the demand of structural enhancement and backwards compatibility of modern BDS navigation signal which is represented by the pilot channel, BDS has proposed several new constant envelope modulations recently, including QMBOC and ADualQPSK modulations applied to B1 band, TD-AltBOC and ACE-BOC modulations applied to B2 band, DualQPSK modulation applied to B3 band, GCE-BOC modulation that multiplexes arbitrary signals at two different carrier frequencies. All the new modulations were systematically analyzed and a unified analytical expression of constant envelope modulation and multiplexing was summarized on the basis of the GCE-BOC modulation, which can provide an important reference for the comprehensive understanding of the signal design of the BDS global navigation satellite system and the development of new type of constant envelope modulation and multiplexing technology on this basis.
For the demand of structural enhancement and backwards compatibility of modern BDS navigation signal which is represented by the pilot channel, BDS has proposed several new constant envelope modulations recently, including QMBOC and ADualQPSK modulations applied to B1 band, TD-AltBOC and ACE-BOC modulations applied to B2 band, DualQPSK modulation applied to B3 band, GCE-BOC modulation that multiplexes arbitrary signals at two different carrier frequencies. All the new modulations were systematically analyzed and a unified analytical expression of constant envelope modulation and multiplexing was summarized on the basis of the GCE-BOC modulation, which can provide an important reference for the comprehensive understanding of the signal design of the BDS global navigation satellite system and the development of new type of constant envelope modulation and multiplexing technology on this basis.
2023, 45(6):84-89.
DOI: 10.11887/j.cn.202306012
Abstract:
Plasma has a unique protective effect against high-power microwave attack. Based on the plasma fluid approximation method, the time dependent evolution of the incident electric field during the interaction between high-power microwaves and columnar plasma arrays was studied by using COMSOL software, and the physical process and mechanism of plasma protection against high-power microwaves were analyzed. The results show that the incident high-power microwave will change the plasma parameters drastically, especially the electron density will increase sharply, so that the plasma will show metal-like electromagnetic properties to the incident high-power microwave, and finally realize the effective protection against the incident high-power microwave. In addition, the plasma protection against high-power microwaves was experimentally verified by using columnar plasma arrays generated by high-frequency glow discharge. Finally, the main problems to be solved for plasma-based high-power microwave protection technology were summarized.
Plasma has a unique protective effect against high-power microwave attack. Based on the plasma fluid approximation method, the time dependent evolution of the incident electric field during the interaction between high-power microwaves and columnar plasma arrays was studied by using COMSOL software, and the physical process and mechanism of plasma protection against high-power microwaves were analyzed. The results show that the incident high-power microwave will change the plasma parameters drastically, especially the electron density will increase sharply, so that the plasma will show metal-like electromagnetic properties to the incident high-power microwave, and finally realize the effective protection against the incident high-power microwave. In addition, the plasma protection against high-power microwaves was experimentally verified by using columnar plasma arrays generated by high-frequency glow discharge. Finally, the main problems to be solved for plasma-based high-power microwave protection technology were summarized.
2017, 39(3):1-6.
DOI: 10.11887/j.cn.201703001
Abstract:
According to the one-dimension design theory of ejector, cooling the secondary flow before it enters into the mixing chamber can promote the eject efficiency and increase the eject coefficient, but flow loss is brought with the addition of precooler, so the performance evaluation of ejector is necessary. Looking on the eject system with precooler, the effect of precooler on the performance of system was analyzed through the onedimension theory, and the effects of the intensifying effect of precooling and the weakening effect of resistance on eject efficiency were analyzed emphatically. The research results indicate that: the precooler brings intensifying effect of precooling and weakening effect of resistance to eject system, and the cross section area and heat transfer area of the precooler are the dominating factors; cross section area of the precooler has a critical value, when the cross section area is bigger than the critical value, the eject performance improves with the increase of heat transfer area, otherwise it worsens; the eject performance of the equivalent pressure mixing scheme is better than that of the equivalent area mixing scheme, the eject coefficient of the former is 60% higher than the latter; precooling improves the eject performance effectively, especially for the equivalent area mixing scheme, the performance is improved by 35.5%.
According to the one-dimension design theory of ejector, cooling the secondary flow before it enters into the mixing chamber can promote the eject efficiency and increase the eject coefficient, but flow loss is brought with the addition of precooler, so the performance evaluation of ejector is necessary. Looking on the eject system with precooler, the effect of precooler on the performance of system was analyzed through the onedimension theory, and the effects of the intensifying effect of precooling and the weakening effect of resistance on eject efficiency were analyzed emphatically. The research results indicate that: the precooler brings intensifying effect of precooling and weakening effect of resistance to eject system, and the cross section area and heat transfer area of the precooler are the dominating factors; cross section area of the precooler has a critical value, when the cross section area is bigger than the critical value, the eject performance improves with the increase of heat transfer area, otherwise it worsens; the eject performance of the equivalent pressure mixing scheme is better than that of the equivalent area mixing scheme, the eject coefficient of the former is 60% higher than the latter; precooling improves the eject performance effectively, especially for the equivalent area mixing scheme, the performance is improved by 35.5%.
2012, 34(4):22-27.
Abstract:
The waverider is considered as an important candidate for the configuration of hypersonic glide vehicle (HGV) in terms of its high lift-to-drag ratio. Due to the severe aerodynamic heating, the sharp leading edge of waverider need be blunted, and the flow characteristics and the aerodynamic performance along the trajectory will change. In the current research, the flow characteristic of a HGV was studied based on a reference trajectory, and a numerical simulation was carried out to evaluate the performance of HGV with a blunt leading edge under a typical condition. The result indicates that the flow near the stagnation point exhibits three-dimensionality which cannot be approximated as a flow around a sphere or cylinder; the heat flux can be reduced and the aerodynamic performance of HGV may decrease as well when the leading edge is blunted: under the condition of 2 cm radii, the lift-to-drag ratio reduces by 12.34%, and different thermal protection methods can be used in different places of HGV.
The waverider is considered as an important candidate for the configuration of hypersonic glide vehicle (HGV) in terms of its high lift-to-drag ratio. Due to the severe aerodynamic heating, the sharp leading edge of waverider need be blunted, and the flow characteristics and the aerodynamic performance along the trajectory will change. In the current research, the flow characteristic of a HGV was studied based on a reference trajectory, and a numerical simulation was carried out to evaluate the performance of HGV with a blunt leading edge under a typical condition. The result indicates that the flow near the stagnation point exhibits three-dimensionality which cannot be approximated as a flow around a sphere or cylinder; the heat flux can be reduced and the aerodynamic performance of HGV may decrease as well when the leading edge is blunted: under the condition of 2 cm radii, the lift-to-drag ratio reduces by 12.34%, and different thermal protection methods can be used in different places of HGV.
6 FlatLFS: a lightweight file system for optimizing the performance of accessing massive small files
2013, 35(2):120-126.
Abstract:
The storage and access of massive small files are one of the challenges in the design of DFS(Distributed file system). Most of the DFSs, such as GFS and HDFS, are designed for handling massive big files. The performance of DFSs decreases greatly when accessing massive small files without special optimization for small files. This research focuses on the optimizing of the performance of data server in handling massive small files, and presents a Flat Lightweight File System called FlatLFS in which the user data are managed flat in disks. FlatLFS is supposed to substitute the traditional file system when accessing user data for upper DFSs. With the improvement of the performance of small data block processing on data servers by FlatLFS, the performance of the whole DFSs is greatly improved. The effectiveness of FlatLFS is proved with intensive experiments: when the size of data block is 1M, the performance of random read of FlatLFS is 135%, 112% and 122% higher than ext 3 ,ext4 and reiserfs respectively.
The storage and access of massive small files are one of the challenges in the design of DFS(Distributed file system). Most of the DFSs, such as GFS and HDFS, are designed for handling massive big files. The performance of DFSs decreases greatly when accessing massive small files without special optimization for small files. This research focuses on the optimizing of the performance of data server in handling massive small files, and presents a Flat Lightweight File System called FlatLFS in which the user data are managed flat in disks. FlatLFS is supposed to substitute the traditional file system when accessing user data for upper DFSs. With the improvement of the performance of small data block processing on data servers by FlatLFS, the performance of the whole DFSs is greatly improved. The effectiveness of FlatLFS is proved with intensive experiments: when the size of data block is 1M, the performance of random read of FlatLFS is 135%, 112% and 122% higher than ext 3 ,ext4 and reiserfs respectively.
2012, 34(5):1-4.
Abstract:
A designing method of supersonic nozzle with controllable contour based on B-Spline curve and characteristic line algorithm is proposed. The contour of the nozzle was adjusted by assigning the distribution of Mach number on the nozzle’s axis. The reliability of the designing method was validated by numerical simulation, which shows that the outflow of the nozzle with high quality can be produced and the contour can be adjusted freely. The result also shows that the nozzle designed by the proposed method can produce better flow than the minimal length nozzle(MLN) with the same length.
A designing method of supersonic nozzle with controllable contour based on B-Spline curve and characteristic line algorithm is proposed. The contour of the nozzle was adjusted by assigning the distribution of Mach number on the nozzle’s axis. The reliability of the designing method was validated by numerical simulation, which shows that the outflow of the nozzle with high quality can be produced and the contour can be adjusted freely. The result also shows that the nozzle designed by the proposed method can produce better flow than the minimal length nozzle(MLN) with the same length.
2012, 34(3):1-5.
Abstract:
The dimension reduction method of the true proportional navigation (TPN) guidance law is proposed. Firstly, the rotation principle of the line of sight (LOS) was investigated, two kinds of angular velocities of LOS were presented, and so were their calculation methods. Then, the LOS kinematic equation was advanced, and the new relative dynamic equation between interceptor and target was proposed. It was found that there is an instantaneous rotation plane of LOS (IRPL) in the three dimensional (3D) space, in which two dimensional (2D) guidance laws can be constructed to serve for 3D interception guidance. The spatial 3D true proportional navigation (TPN) guidance law was directly introduced into IRPL without any approximation and linearization to transform into dimension reduced 2D TPN, and the characteristics were studied. Finally, an exoatmospheric interception was taken for simulation to demonstrate the effectiveness of the theory presented in this paper.
The dimension reduction method of the true proportional navigation (TPN) guidance law is proposed. Firstly, the rotation principle of the line of sight (LOS) was investigated, two kinds of angular velocities of LOS were presented, and so were their calculation methods. Then, the LOS kinematic equation was advanced, and the new relative dynamic equation between interceptor and target was proposed. It was found that there is an instantaneous rotation plane of LOS (IRPL) in the three dimensional (3D) space, in which two dimensional (2D) guidance laws can be constructed to serve for 3D interception guidance. The spatial 3D true proportional navigation (TPN) guidance law was directly introduced into IRPL without any approximation and linearization to transform into dimension reduced 2D TPN, and the characteristics were studied. Finally, an exoatmospheric interception was taken for simulation to demonstrate the effectiveness of the theory presented in this paper.
2016, 38(6):1-5.
DOI: 10.11887/j.cn.201606001
Abstract:
Electromagnetic launch technology is an inevitable trend among methods of launch in the future. The principle and technology characteristics of electromagnetic launch is analyzed, three branches of electromagnetic launch technology development overseas in electromagnetic ejection, electromagnetic railgun and electromagnetic pushing were studied, and the key technology of electromagnetic launch was summarized. Furthermore, the development strategy and the extension application prospect of electromagnetic launch technology was proposed.
Electromagnetic launch technology is an inevitable trend among methods of launch in the future. The principle and technology characteristics of electromagnetic launch is analyzed, three branches of electromagnetic launch technology development overseas in electromagnetic ejection, electromagnetic railgun and electromagnetic pushing were studied, and the key technology of electromagnetic launch was summarized. Furthermore, the development strategy and the extension application prospect of electromagnetic launch technology was proposed.
2017, 39(3):15-22.
DOI: 10.11887/j.cn.201703003
Abstract:
The basic problem of gliding guidance for hypersonic vehicles was proposed, and the difficulties of complicated multiple constraints, maneuver requirements, and parameter perturbation in the course of gliding guidance were analyzed. The corresponding research status at home and abroad was surveyed, and the problems were also pointed out. On this basis, the key problems required to be solved at present in the research of gliding guidance for hypersonic vehicles were presented, and the research hotspots in the methods of future gliding guidance were also pointed out.
The basic problem of gliding guidance for hypersonic vehicles was proposed, and the difficulties of complicated multiple constraints, maneuver requirements, and parameter perturbation in the course of gliding guidance were analyzed. The corresponding research status at home and abroad was surveyed, and the problems were also pointed out. On this basis, the key problems required to be solved at present in the research of gliding guidance for hypersonic vehicles were presented, and the research hotspots in the methods of future gliding guidance were also pointed out.
2013, 35(2):7-11.
Abstract:
The relationship of coefficient of pressure center of body of revolution and angle-of-attack and Mach number was educed, based on the aerodynamic formulas of high-angle-of-attack flow. Adopting a k-ε two-equation turbulence model following the realizable rules, seven kinds of body of revolution with different shapes in high-angle-of-attack flow fields were researched by means of CFD, and the numerical results were derived. The numerical simulation results were consistent with the ones in theoretic analysis. Research results indicate that there is a geometric discriminant, which is correlated with the geometric configuration that has strong influence on the law of variation of the coefficient of pressure center.
The relationship of coefficient of pressure center of body of revolution and angle-of-attack and Mach number was educed, based on the aerodynamic formulas of high-angle-of-attack flow. Adopting a k-ε two-equation turbulence model following the realizable rules, seven kinds of body of revolution with different shapes in high-angle-of-attack flow fields were researched by means of CFD, and the numerical results were derived. The numerical simulation results were consistent with the ones in theoretic analysis. Research results indicate that there is a geometric discriminant, which is correlated with the geometric configuration that has strong influence on the law of variation of the coefficient of pressure center.
2013, 35(2):104-108.
Abstract:
In global navigation satellite system (GNSS) receivers, matched filters should be applied in time delay estimation to maximize signal-to-noise ratio of tracking loops. Integrate and dump filters are often used as a simplification to reduce hardware cost; however, there is no quantitative conclusion about its performance degradation yet. To deal with this issue, analytical expression of performance degradation is derived, and Monte Carlo simulations are given to support the analysis. Theoretical and simulated results show that the performance degradation is about 0.44dB if sampling frequency is twice of signal bandwidth, and it can be neglected if sampling frequency is increased to four times of signal bandwidth.
In global navigation satellite system (GNSS) receivers, matched filters should be applied in time delay estimation to maximize signal-to-noise ratio of tracking loops. Integrate and dump filters are often used as a simplification to reduce hardware cost; however, there is no quantitative conclusion about its performance degradation yet. To deal with this issue, analytical expression of performance degradation is derived, and Monte Carlo simulations are given to support the analysis. Theoretical and simulated results show that the performance degradation is about 0.44dB if sampling frequency is twice of signal bandwidth, and it can be neglected if sampling frequency is increased to four times of signal bandwidth.
2013, 35(2):132-136.
Abstract:
Many information retrieval applications have to present their results in the form of ranked lists, in which documents must be sorted in a descending order according to their relevance to a given query. This has led the interest of the information retrieval community in methods that automatically learn effective ranking models, and recently machine learning techniques have also been applied to model construction. Most of the existing methods do not take into consideration the fact that significant homogeneity exists between query-document pairs related to user’s feedback. In this research, a novel method which clusters patterns in the training data with their relevance from the user, and then uses the discovered rules to rank documents at query-time. A systematic evaluation of the proposed method using the LETOR benchmark dataset is posposed. The experimental results show that the proposed method outperforms the state-of-the-art methods with no need of time-consuming and laborious pre-processing.
Many information retrieval applications have to present their results in the form of ranked lists, in which documents must be sorted in a descending order according to their relevance to a given query. This has led the interest of the information retrieval community in methods that automatically learn effective ranking models, and recently machine learning techniques have also been applied to model construction. Most of the existing methods do not take into consideration the fact that significant homogeneity exists between query-document pairs related to user’s feedback. In this research, a novel method which clusters patterns in the training data with their relevance from the user, and then uses the discovered rules to rank documents at query-time. A systematic evaluation of the proposed method using the LETOR benchmark dataset is posposed. The experimental results show that the proposed method outperforms the state-of-the-art methods with no need of time-consuming and laborious pre-processing.
2012, 34(4):126-131.
Abstract:
A novel structured dictionary training algorithm is proposed for double sparse image representation. Based on the double sparse image representation model proposed by Rubinstein, the zero-tree structure of wavelet coefficients was introduced, and the new dictionary atoms were constructed by linear combination of wavelet bases in all high-frequency bands of same orientation across different scales. The linear combination coefficients were learned via K-SVD. The image decomposition and reconstruction algorithm was proposed based on the learned dictionary. The M-term approximation and compression of remote sensing images both proved the better effects of the proposed structured dictionary than the existing dictionaries.
A novel structured dictionary training algorithm is proposed for double sparse image representation. Based on the double sparse image representation model proposed by Rubinstein, the zero-tree structure of wavelet coefficients was introduced, and the new dictionary atoms were constructed by linear combination of wavelet bases in all high-frequency bands of same orientation across different scales. The linear combination coefficients were learned via K-SVD. The image decomposition and reconstruction algorithm was proposed based on the learned dictionary. The M-term approximation and compression of remote sensing images both proved the better effects of the proposed structured dictionary than the existing dictionaries.
2023, 45(1):57-66.
DOI: 10.11887/j.cn.202301006
Abstract:
Matrix transpose is one of the common matrix operations, which is widely employed in various fields such as signal processing, scientific computing, and deep learning. With the popularization of Phytium heterogeneous multi-core DSPs(digital signal processors) developed by National University of Defense Technology, there is a strong demand for high-performance matrix transpose implementations for Phytium multi-core DSPs. Based on the architecture of multi-core DSPs and the characteristic of matrix transpose operations, a parallel matrix transpose algorithm (called ftmMT) for matrices with different element bit widths (8 B, 4 B, and 2 B) was proposed. In ftmMT, the main optimizations include vectorization based on vector Load/Store functions, core-level parallelization based on matrix blocking, and overlapping between vectorization and memory access through implicit ping-pong methods. The experimental results show that ftmMT can significantly improve the performance of matrix transpose operations, and achieve a speedup of up to 8.99 times in comparison with the open-source transpose library HPTT running on CPU.
Matrix transpose is one of the common matrix operations, which is widely employed in various fields such as signal processing, scientific computing, and deep learning. With the popularization of Phytium heterogeneous multi-core DSPs(digital signal processors) developed by National University of Defense Technology, there is a strong demand for high-performance matrix transpose implementations for Phytium multi-core DSPs. Based on the architecture of multi-core DSPs and the characteristic of matrix transpose operations, a parallel matrix transpose algorithm (called ftmMT) for matrices with different element bit widths (8 B, 4 B, and 2 B) was proposed. In ftmMT, the main optimizations include vectorization based on vector Load/Store functions, core-level parallelization based on matrix blocking, and overlapping between vectorization and memory access through implicit ping-pong methods. The experimental results show that ftmMT can significantly improve the performance of matrix transpose operations, and achieve a speedup of up to 8.99 times in comparison with the open-source transpose library HPTT running on CPU.
2013, 35(2):75-80.
Abstract:
In the condition of navigation war, civil or indoor environment, when the visible satellite number is less than 3 and users’ position is unknown, one-way timing solution is no longer unavailable. Based on the characteristics of Chinese navigation satellite system such as COMPASS and CAPS, a doppler positioning timing method based on IGSO satellite is proposed. By measuring the doppler frequency shift and counting the integral Doppler, the user position and time are computed. Analysis result shows that the positing and timing usability can reach nearly 100% in Chinese domain when using 3 IGSO satellites with transponders. The position precision can achieve 3m and the timing error is less than 100ns for static users with long time measurement. Because only one IGSO satellite is needed and there is no requirement for demodulating navigation message, this method provides a novel timing method for the navigation war background and weak signal environment.
In the condition of navigation war, civil or indoor environment, when the visible satellite number is less than 3 and users’ position is unknown, one-way timing solution is no longer unavailable. Based on the characteristics of Chinese navigation satellite system such as COMPASS and CAPS, a doppler positioning timing method based on IGSO satellite is proposed. By measuring the doppler frequency shift and counting the integral Doppler, the user position and time are computed. Analysis result shows that the positing and timing usability can reach nearly 100% in Chinese domain when using 3 IGSO satellites with transponders. The position precision can achieve 3m and the timing error is less than 100ns for static users with long time measurement. Because only one IGSO satellite is needed and there is no requirement for demodulating navigation message, this method provides a novel timing method for the navigation war background and weak signal environment.
2017, 39(3):7-14.
DOI: 10.11887/j.cn.201703002
Abstract:
Space solar power station is a kind of space structure with large size and high flexibility. It is far larger than the previous spacecraft in size, which results in new phenomena and new problems on the study of dynamical characteristics. The kilometerscale dumbbell model was studied. The Hamilton’s dynamical model on orbit was established under the effect of gravity gradient. The symplectic Runge-Kutta method was used with different combinations of parametrical values to obtain dynamical responses. By comparing the simulation results, the quantitative relationships were determined respectively between the size of space structure and the effect of gravity gradient on orbital motion and attitude motion. It is found that: due to the gravity gradient, the coupling phenomenon between attitude motion and elastic vibration occurs; the attitude motion has great influence on the external envelope curve of elastic vibration response, while the period of it is changed by elastic vibration.
Space solar power station is a kind of space structure with large size and high flexibility. It is far larger than the previous spacecraft in size, which results in new phenomena and new problems on the study of dynamical characteristics. The kilometerscale dumbbell model was studied. The Hamilton’s dynamical model on orbit was established under the effect of gravity gradient. The symplectic Runge-Kutta method was used with different combinations of parametrical values to obtain dynamical responses. By comparing the simulation results, the quantitative relationships were determined respectively between the size of space structure and the effect of gravity gradient on orbital motion and attitude motion. It is found that: due to the gravity gradient, the coupling phenomenon between attitude motion and elastic vibration occurs; the attitude motion has great influence on the external envelope curve of elastic vibration response, while the period of it is changed by elastic vibration.
2014, 36(1):6-10.
DOI: 10.11887/j.cn.201401002
Abstract:
A compressible flow heterogeneous parallel solver based on MPI+CUDA on CPU/GPU heterogeneous system was established. Then different parallel computing models and optimizing methods of compressible flow parallel computing algorithm were discussed. This solver runs different codes with difference resources: the codes which are complex or have low computing density are run on CPU, while the codes which are simple or have high computing density are run on GPU. The heterogeneous systems’ computing results and the efficiencies with homogeneous systems were compared through several problems. Finally, the heterogeneous algorithm was applied to the hypersonic flow. The result shows that the algorithm is robust and the computing efficiency is improved ten times more than that of the homogeneous algorithm.
A compressible flow heterogeneous parallel solver based on MPI+CUDA on CPU/GPU heterogeneous system was established. Then different parallel computing models and optimizing methods of compressible flow parallel computing algorithm were discussed. This solver runs different codes with difference resources: the codes which are complex or have low computing density are run on CPU, while the codes which are simple or have high computing density are run on GPU. The heterogeneous systems’ computing results and the efficiencies with homogeneous systems were compared through several problems. Finally, the heterogeneous algorithm was applied to the hypersonic flow. The result shows that the algorithm is robust and the computing efficiency is improved ten times more than that of the homogeneous algorithm.
2024, 46(1):93-102.
DOI: 10.11887/j.cn.202401010
Abstract:
Traditional Yinyang K-means algorithm is computationally expensive when dealing with large-scale clustering problems. An efficient parallel acceleration implementation of Yinyang K-means algorithm was proposed on the basis of the architectural characteristics of typical many-core CPUs. This implementation was based on a new memory data layout, used vector units in many-core CPUs to accelerate distance calculation in Yinyang K-means, and targeted memory access optimization for NUMA(non-uniform memory access) characteristics. Compared with the open source multi-threaded version of Yinyang K-means algorithm, this implementation can achieve the speedup of up to 5.6 and 8.7 approximately on ARMv8 and x86 many-core CPUs, respectively. Experiments show that the optimization successfully accelerate Yinyang K-means algorithm in many-core CPUs.
Traditional Yinyang K-means algorithm is computationally expensive when dealing with large-scale clustering problems. An efficient parallel acceleration implementation of Yinyang K-means algorithm was proposed on the basis of the architectural characteristics of typical many-core CPUs. This implementation was based on a new memory data layout, used vector units in many-core CPUs to accelerate distance calculation in Yinyang K-means, and targeted memory access optimization for NUMA(non-uniform memory access) characteristics. Compared with the open source multi-threaded version of Yinyang K-means algorithm, this implementation can achieve the speedup of up to 5.6 and 8.7 approximately on ARMv8 and x86 many-core CPUs, respectively. Experiments show that the optimization successfully accelerate Yinyang K-means algorithm in many-core CPUs.
2015, 37(1):21-27.
DOI: 10.11887/j.cn.201501004
Abstract:
Computing unsatisfiable subformulas of Boolean formulas has practical applications in VLSI design and verification. The unsatisfiable subformulas can help electronic design automation tools to rapidly locate the errors and inconsistency. The definitions of resolution refutation and refutation parsing tree, and a heuristic local search algorithm to extract unsatisfiable subformulas from the resolution refutation of a formula are presented. The approach directly constructs the refutation parsing tree for proving unsatisfiability with a local search procedure, and then recursively derives unsatisfiable subformulas. The algorithm combines with reasoning heuristics, dynamic pruning and subsumption elimination method to improve the efficiency. The experimental results show that our algorithm outperforms the similar algorithms on the random benchmarks.
Computing unsatisfiable subformulas of Boolean formulas has practical applications in VLSI design and verification. The unsatisfiable subformulas can help electronic design automation tools to rapidly locate the errors and inconsistency. The definitions of resolution refutation and refutation parsing tree, and a heuristic local search algorithm to extract unsatisfiable subformulas from the resolution refutation of a formula are presented. The approach directly constructs the refutation parsing tree for proving unsatisfiability with a local search procedure, and then recursively derives unsatisfiable subformulas. The algorithm combines with reasoning heuristics, dynamic pruning and subsumption elimination method to improve the efficiency. The experimental results show that our algorithm outperforms the similar algorithms on the random benchmarks.
