ISSN 1000-1239 CN 11-1777/TP

Table of Content

01 May 2015, Volume 52 Issue 5
SIMD-Based Inverted Index Compression Algorithms
Yan Hongfei, Zhang Xudong, Shan Dongdong, Mao Xianling, Zhao Xin
2015, 52(5):  995-1004.  doi:10.7544/issn1000-1239.2015.20131548
Asbtract ( 1108 )   HTML ( 3)   PDF (2698KB) ( 529 )  
Related Articles | Metrics
The rapid growth of text information has brought about new challenges to traditional information retrieval. In large search engines, indexing is required to help users acquire important data they need, and techniques of inverted index have great influence on the efficiency of query processing in such systems. The data in inverted index is stored in the form of arrays of integers, and techniques of compression are required to reduce the cost of storing such data in disks and memory, as well as to boost the hit rate of CPU cache and speed up transferring data. Therefore, it is necessary to choose a highly efficient compression algorithm to process query effectively. In this paper, we propose two instruction-level-parallelized algorithms, i.e. SIMD-PB and SIMD-PFD, which improve two competitive compression algorithms respectively, i.e. PackedBinary and PForDelta, and exploit SIMD instructions to accelerate the Pack and Unpack procedure in the algorithms. Experiments based on public datasets of GOV2 and ClueWeb09B show that our novel algorithms have good performance on encoding and decoding speed without impairing the compression ratio, and outperform the former fastest inverted list compression algorithms by at most 17%, with respect to decompression speed. Furthermore, experiments indicate that our novel algorithms have better performance on longer posting list and larger block size w.r.t. decoding speed.
Chinese Text Deception Detection Based on Ensemble Learning
Zhang Hu, Tan Hongye, Qian Yuhua, Li Ru, Chen Qian
2015, 52(5):  1005-1013.  doi:10.7544/issn1000-1239.2015.20131552
Asbtract ( 954 )   HTML ( 0)   PDF (1751KB) ( 568 )  
Related Articles | Metrics
Deception detection is important in the field of information security. Existing researches show that one third of the interpersonal communication involves the potential deceptions, and there are large amounts of deceptive messages in the more and more Web information. If the deception is potentially dangerous to people's life, the survival of enterprise and the stability of the country, then the negligence of deception may lead to incalculable loss. In the massive amounts of information the scale of the non-deceptive texts is much larger than the scale of the deceptive texts, so people remain unsuccessful and inefficient in detecting those deceptive messages by the existing methods, and it is desirable to create an automated method which could help people flag the possible deceptive messages. In this paper, we built a deception detection model based on ensemble learning to solve the imbalance of the existing data sets. Firstly a novel bisecting k-means method is proposed to cut the training sample set, and the separate classifiers are trained by using each pair of positive and negative samples, and then each test sample category value is calculated by the classifiers, and finally a novel min-max modular approach is used to integrate each category result. Experimental results verify the effectiveness of this method.
Community Hot Statuses Recommendation
Peng Zehuan, Sun Le, Han Xianpei, Chen Bo
2015, 52(5):  1014-1021.  doi:10.7544/issn1000-1239.2015.20131551
Asbtract ( 779 )   HTML ( 0)   PDF (1793KB) ( 734 )  
Related Articles | Metrics
Micro-blog recommendation is an effective technique to resolve the information overload problem in micro-blog systems. In this paper, we summarize and model several key factors which affect a user's interest on a specific status, including implicit features, content features (i.e., content similarity, user tags, and user's favorites), social network features, and status features. Based on the above features, we propose a community hot status recommendation algorithm—CMR (community micro-blog recommendation), which combines both explicit features and implicit features for better recommendation. Specifically, we propose a learning method to rank based framework, which learns a user's interest model of status from his preference data, including his retweets, favorites, comments, etc. Then new statuses are scored and ranked using the learned interest model. In order to measure our method's performance, we conduct a series of experiments in three community data sets (including NLP, Photography and Basketball). Experimental results show that: 1)by combining both implicit features and explicit features, our method achieves better recommendation performance than that using a single type of features; 2) compared with the MRR (micro-blog repost rank based recommendation), CMR gets better recommendation performance; 3) MRR prefers recommending hot statuss in the whole micro-blog system, in contrast CMR usually recommends community-specific statuses.
Microblog Bursty Topic Detection Method Based on Momentum Model
He Min, Du Pan, Zhang Jin, Liu Yue, Cheng Xueqi
2015, 52(5):  1022-1028.  doi:10.7544/issn1000-1239.2015.20131549
Asbtract ( 790 )   HTML ( 1)   PDF (1342KB) ( 929 )  
Related Articles | Metrics
Microblogs reflect the general public's real-time reaction to major events. Finding bursty topics from microblogs is an important task to understand the current events which attract a large number of Internet users. However, the existing methods suitable for news articles aren't adopted directly for microblogs, because microblogs have unique characteristics compared with formal texts, including diversity, dynamic and noise. In this paper, a new detection method for microblog bursty topic is proposed based on momentum model. The meaningful strings are extracted from micorblog posts in the special time window as the microblog dynamic features. The dynamic characteristics of these features are modeled by the principle of momentum. The velocity, accelerated velocity and momentum of the features are defined by the dynamic frequencies at different dimensions. The bursty features are detected with the combination of momentum, variation trend and second order change rate. By merging the detected bursty features with mutual information, the bursty topics are obtained. The experiments are conducted on a real Sina microblog data set containing around 526 thousand posts of 1000 users, and results show that the proposed method improves the precision and recall remarkably compared with the conventional methods. The proposed method could be well applied in online bursty topic detection for microblog information.
Unsupervised Chinese Open Entity Relation Extraction
Qin Bing, Liu Anan, Liu Ting
2015, 52(5):  1029-1035.  doi:10.7544/issn1000-1239.2015.20131550
Asbtract ( 1838 )   HTML ( 7)   PDF (1277KB) ( 2140 )  
Related Articles | Metrics
Entity relation extraction is an important task in information extraction which helps people find knowledge quickly and accurately in various text. Traditionally, entity relation extraction methods require a pre-defined set of relation types and a corpus with manual tags. But it is difficult to build a well-defined architecture of the relation types and it takes a lot of time to label a corpus. Open entity relation extraction is the task of extracting relation triples from natural language text without pre-defined relation types. There is a lot of research in the field of English open entity relation extraction, but rarely in the field of Chinese open entity relation extraction. This paper presents the UnCORE (unsupervised Chinese open entity relation extraction method for the Web). UnCORE is an unsupervised open entity relation extraction method which discovers relation triples from large-scale Web text. UnCORE exploits using word distance and entity distance constraints to generate candidate relation triples from the raw corpus, and then adopts global ranking and domain ranking methods to discover relation words from the candidate relation triples. Finally UnCORE filters candidate relation triples by using the extracted relation words and some sentence rules. Results show that UnCORE extracts large scale relation triples at precision higher than 80%.
Agent-Based Artificial Society Modeling Language
Tang Mingsheng, Mao Xinjun, Zhou Huiping
2015, 52(5):  1036-1049.  doi:10.7544/issn1000-1239.2015.20131564
Asbtract ( 964 )   HTML ( 4)   PDF (4831KB) ( 586 )  
Related Articles | Metrics
ACP(artificial societies, computational experiments, and parallel execution) is a classic social computing approach to research on complex social issues like emergency management, and artificial society modeling is the foundation of this approach.Artificial societies are the mappings of real social systems in the computer world, with the characteristics of complexity, multiplicity, multilevel, sociality, and so forth.Hence, how to support artificial societies modeling becomes an important research topic.Synthetically considering the characteristics of artificial societies and the artificial society modeling requirements of emergency management and ACP approach, an artificial society modeling language (ASML) is proposed, and its meta-model, multiple-viewpoint models and graphic modeling language are also detailed.ASML is based on the technology of multi-agent systems and inspired from the social organization theory, which facilitates analyzing and modeling artificial society in a high-level abstraction, natural and easy-to-understand way.The rigorous semantics foundation of ASML makes model checking and model transforming possible.In addition, the developed supporting software toolkits ASMLTools support artificial society modeling with ASML, ASML model checking and model transforming, etc.Through a case study its effectiveness and usability are demonstrated.
Review Selection Considering Opinion Diversity
Yu Wenzhe, Sha Chaofeng, He Xiaofeng, Zhang Rong
2015, 52(5):  1050-1060.  doi:10.7544/issn1000-1239.2015.20131932
Asbtract ( 700 )   HTML ( 1)   PDF (2981KB) ( 542 )  
Related Articles | Metrics
Online user-generated reviews provide consumers with abundant information, which influences their shopping decisions on a variety of products from daily consumption to entertainment. Due to the sheer size of the reviews, users are prevented from a clear picture of products. In fact, it is not easy for them to go through all reviews for each item. Existing solutions to information overload in ecommerce sites include estimating the quality of reviews and summarizing the opinions from the reviews. However, review ranking based on review quality may lead to information redundancy while review summarization fails to provide the context of reviews, resulting in poor readability. To this end, the paper aims at implementing an effective review selection method. We design two opinion extraction algorithms, which are dictionary and rule-based, and LDA-based respectively, to represent each review. A greedy approach is proposed to select a small set of high quality reviews for each product, and to maximize both the attribute coverage and opinion diversity. A set of experimental results on real datasets show that the proposed method is effective, and for the two opinion extraction algorithms, the dictionary and rule-based algorithm performs better than the LDA-based algorithm in solving review selection problem.
Materialization Strategies in Big Data Analysis System Based on Column-Store
Zhang Bin, Le Jiajin, Sun Li, Xia Xiaoling, Wang Mei, Li Yefeng
2015, 52(5):  1061-1070.  doi:10.7544/issn1000-1239.2015.20140693
Asbtract ( 907 )   HTML ( 5)   PDF (2920KB) ( 513 )  
Related Articles | Metrics
The characters of big data are volume, variety, velocity, common hardware and open source. In traditional relational database, materialization can speed up query processing greatly. However, modern big data analysis faces a confluence of growing challenges that systems become more and more inefficiently and scalability. Consequently, this paper presents some materialization strategies based on column-store to provide an effective environment for big data analysis. Firstly, it analyzes the impact of materialization efficiency by MapReduce cost model. Secondly, it designs the MapReduce column-store File, and achieves optimization by cooperative localization strategy. Fourthly, according to the different materialization time window, it proposes materialization strategies in MapReduce based on column-store (MSMC), which is composed of three strategies: MapReduce early materialization strategy (MEMS), MapReduce late materialization strategy (MLMS) and MapReduce early-late materialization strategy (MELMS). Thirdly, for the sake of avoiding malignant expansion of materialization sets, it designs the adaptive materialization sets adjust strategy(AMSAS), which realizes the optimization of MSMC effectively. Finally, the experiments are conducted to evaluate execution time and load capacity. The results reveal that the materialization strategies in MapReduce based on column-store and adaptive materialized set adjustment strategy can effectively reduce the intermediate data process of MapReduce, network bandwidth and unnecessary I/O. It verifies the effectiveness of the proposed method in big data analysis.
Concept Drifting Detection for Categorical Evolving Data Based on Parallel Reducts
Deng Dayong, Xu Xiaoyu, Huang Houkuan
2015, 52(5):  1071-1079.  doi:10.7544/issn1000-1239.2015.20140275
Asbtract ( 770 )   HTML ( 0)   PDF (2543KB) ( 593 )  
Related Articles | Metrics
Data stream mining is one of the hot topics of data mining and concept drifting detection is one of its research directions. There have been many methods to detect concept drifting, but there are some drawbacks in current methods to detect concept drifting, such as no reducing redundant attributes integrally in sliding windows, and detecting concept drifting according to outer properties, etc. Based on the basic principles of rough sets and F-rough sets, the sliding windows in a data stream are regarded as decision subsystems, and the attribute significance of conditional attributes is used to detect concept drifting. This new method is divided into two steps: the redundant attributes in a streaming data are reduced through parallel reducts at first, then the concept drifting is detected according to the change of attribute significance. Different from other existing methods, the inner properties of data stream are used to detect concept drifting. Experiments show that this method is valid to reduce redundant attributes integrally and detect concept drifting, and that the attribute significance based on the mutual information is more effective than the attribute significance based on the positive region when they are used to detect concept drifting. For data stream mining, this paper provides a new method to detect concept drifting. For rough set theory, this paper offers a new application area.
Collaborative-Degree Based Distributed Automatic Negotiation Coalition Formation Mechanism
Hu Jun, Zhang Zhenxing, Zou Li
2015, 52(5):  1080-1090.  doi:10.7544/issn1000-1239.2015.20131544
Asbtract ( 659 )   HTML ( 1)   PDF (1811KB) ( 572 )  
Related Articles | Metrics
Most of current researches on coalition formation do not take into account the heterogeneity of collaboration resources and collaborative attitude of Agents, but assume that all Agents have same collaboration resources and attitude. Apparently that assumption is too restrictive and unrealistic. To this end, a collaborative degree-based distributed automatic negotiation coalition formation mechanism is proposed in this paper. This mechanism consists of three main parts: collaborative degree, distributed negotiation protocol (DNP) and negotiation strategy. At first, the concept of collaborative degree is introduced with the collaboration of resources and collaborative attitude description in network topology. Next, in order to solve the synchronization problem of information flow in distributed application environment, a distributed negotiation protocol is established to achieve distributed auto-negotiation way to build coalition, which can guarantee the convergence of negotiation and do not deadlock. Then, the negotiation strategy based on the degree of collaboration is established to reflect the differences of Agent collaboration resources and collaborative attitude. So, this mechanism establishes distributed negotiation protocols and introduces Agent collaboration degree, and proposes the negotiation strategy based on the degree of collaboration. Finally, experiment results show that the coalition formation efficiency, negotiation efficiency and individual utility of the mechanism are better than other related mechanisms.
Constraint Solving Based on the Number of Instantiation
Li Zhanshan, Zhang Qian, Zhang Liang
2015, 52(5):  1091-1097.  doi:10.7544/issn1000-1239.2015.20131588
Asbtract ( 755 )   HTML ( 0)   PDF (1415KB) ( 553 )  
Related Articles | Metrics
Heuristics is an important topic in the domain of constraint satisfaction problems. Effective heuristics can improve the efficiency of the search algorithms quite a lot. As a result, lots of heuristics to solve the constraint satisfaction problems are presented. Heuristics are divided into many types depending on the acquisition and application of heuristic information, and the main heuristics include variable ordering heuristics and value ordering heuristics. When solving the constraint satisfaction problems, we find that the failed numbers of instantiating a variable reflect the conflict between this variable and the instantiated set, and that the successful numbers of assigning a value reflect the possibility for this value of composing a local solution with the instantiated set. Both numbers have a great influence upon the efficiency of solving constraint satisfaction problems. Based on the above research conclusions, this paper proposes a method of counting the weight number of instantiation and a heuristic of instantiation number combined with the existing mainstream heuristics, and then presents a new corresponding constraint solving algorithm called MAC_Try. We prove that the worst-case time complexity is O(ned3) on a branch. A large number of experimental results show that our proposed algorithm MAC_Try is more effective than the popular constraint solving method MAC3rm.
Parallel Support Vector Machine Training with Hybrid Programming Model
Li Tao, Liu Xuechen, Zhang Shuai, Wang Kai, Yang Yulu
2015, 52(5):  1098-1108.  doi:10.7544/issn1000-1239.2015.20131492
Asbtract ( 678 )   HTML ( 1)   PDF (2430KB) ( 612 )  
Related Articles | Metrics
Support vector machine (SVM) is a supervised method that is widely used in statistical classification and regression analysis. The interior point method (IPM) based SVM training is prominent in the low memory space and the fast convergence. However, it is still confronted with the challenges of training speed and storage space with the increasing size of training dataset. In this paper, the hybrid parallel SVM training mechanism is proposed to alleviate these problems on the CPU-GPU heterogeneous system. Firstly, the computing intensive operation in IPM algorithm is implemented with compute unified device architecture (CUDA). Then the IPM based SVM training algorithm is modified and implemented using cuBLAS library to further improve the training speed. Secondly, the modified IPM based SVM training algorithm is implemented with message passing interface (MPI) and CUDA hybrid programming model on a four-node cluster system. The training time and memory requirement are both reduced at the same time. Finally, the limitation of GPU device memory is eliminated based on the page-locked host memory supported by Fermi architecture. The large datasets are trained efficiently with the size larger than what the GPU memory allows. The results show that the hybrid parallel SVM training mechanism achieves more than 4 times speedup with MPI and CUDA hybrid programming model, and breaks away the GPU device memory limitation with the page-locked host memory based data storage strategy for large-scale SVM training.
Information Technology for Energy Internet: A Survey
Wang Jiye, Meng Kun, Cao Junwei, Cheng Zhihua, Gao Lingchao, Lin Chuang4,5
2015, 52(5):  1109-1126.  doi:10.7544/issn1000-1239.2015.20131592
Asbtract ( 1017 )   HTML ( 1)   PDF (4085KB) ( 1110 )  
Related Articles | Metrics
The drastic increasing demand for energy aggravates the shortage of energy state. Using green renewable energy paves a way to solve the above problem, however, how to access and control these types of intermittent energy faces more challenges. Energy Internet (or Internet of energy), differentiated from the Internet of only transferring and sharing information, has been forecasted as a typical representative of the coming industry revolution. Comparing with the Internet, energy Internet must have the ability of efficiently managing the energy lifecycle including energy production, energy transmission and distribution, and energy consumption. Its objective contains conveniently switching in and switching out, efficiently dispatching energy and dedicatedly fulfilling all consumers' demand etc. In this paper, we analyze the potential requirements of the future energy system, state the related concepts and characters of energy Internet, survey all results with respect to the information technology in energy Internet,and conclude an energy Internet infrastructure and its support technologies. In addition, we discuss the opportunities and challenges of information technology during developing the energy Internet.
MDCent:A Modular Data Center Interconnection with High Scalability and High Performance
Lu Feifei, Zhu Guiming, Tao Zhirong, Xie Xianghui, Guo Deke
2015, 52(5):  1127-1136.  doi:10.7544/issn1000-1239.2015.20140043
Asbtract ( 815 )   HTML ( 0)   PDF (4453KB) ( 471 )  
Related Articles | Metrics
A fundamental goal of data-center networking is to efficiently interconnect a large number of servers with low equipment cost while keeping high network bandwidth. Some server-centric data center networking structures are proposed to tackle the performance bottleneck and the extensibility problems that the traditional tree-based networking schemes are born with. Shipping-container-based data centers are introduced as building blocks for constructing mega-data centers. However, it is a challenge how to interconnect those containers to make sure that the network among the containers has both high scalability and high performance. As a new server-centric network architecture, BCube is able to interconnect thousands of servers into a container and provide high bandwidth for typical traffic patterns. This paper presents a networking architecture among containers called MDCent, which is based on BCube to interconnect servers inside a container. MDCent makes the network among containers have both high scalability and performance on condition that each container makes use of a lot of unused up-link ports and has a fixed degree.
Prediction Method for Network Traffic Based on Genetic Algorithm Optimized Echo State Network
Tian Zhongda, Gao Xianwen, Li Shujiang, Wang Yanhong
2015, 52(5):  1137-1145.  doi:10.7544/issn1000-1239.2015.20131757
Asbtract ( 1036 )   HTML ( 4)   PDF (3341KB) ( 745 )  
Related Articles | Metrics
Network traffic prediction is an important problem of network congestion control and network management. Network traffic time series have time-varying and nonlinear characteristics, So the prediction accuracy of traditional time series prediction method is relatively low and it is unable to establish accurate prediction model. Echo state network (ESN) has good performance in prediction and modeling of nonlinear chaotic system and is very suitable for network traffic time series prediction problem. In order to improve the prediction accuracy of network traffic, the network traffic nonlinear prediction method based on genetic algorithm optimized echo state network is proposed. Firstly, echo state network is used for network traffic predicton, then the genetic algorithm is used to optimize the parameters of the reservoir of the echo state network prediction model. Finally, the prediction accuracy of the prediction model is improved. The actual network traffic data from China Unicom in Liaoning Province is used for simulation verification. Three common prediction models including auto regressive integrated moving average (ARIMA) prediction model, Elman neural network prediction model and least square support vector machine (LSSVM) prediction model are compared, and the simulation results show that the proposed method has higher prediction accuracy with smaller prediction error and it can describe the network traffic characteristics of complex changes.
Impact of System Noise by Quantitative Analysis
Wu Linping, Wei Yong, Xu Xiaowei, Liu Xu
2015, 52(5):  1146-1152.  doi:10.7544/issn1000-1239.2015.20131921
Asbtract ( 743 )   HTML ( 0)   PDF (1346KB) ( 490 )  
Related Articles | Metrics
More attention should be paid on system noise for large-scale parallel application, although the system noise has little impact on one process. One quantitative analysis method for system noise's impact named FWQ-MPI is presented. Four quantitative indicators are given: the proportion of the amount of noise, the proportion of noise impact, the actual/ideal ratio of communication to calculation time. Three iterative methods are selected as the research objects and the micro benchmarks run on a MPP machine with 512 Double six-core nodes. The test results show the impact mechanism of system noise on parallel program performance, and also show several characterizations of system noise as follows. 1)The proportion of the amount of noise is relatively small, accounting for the entire computing time 2% to 6%; 2)But the system noise has much impact( when the parallel scale is 1024,2048 and 4096, the proportion of noise impact is about 30% to 70%); 3)The impact of system noise will be increased when the parallel scale increases, will be decreased when the amount of calculation increases; 4)The impact of system noise is mainly reflected by the “actual ratio of communication to calculation time” is far less than the “ideal ratio of communication to calculation time”.
Parallel Computation for Elastic Mechanical Numerical Simulation on Unstructured Mesh
Zhao Weibo, Liu Qingkai, Yang Yang
2015, 52(5):  1153-1159.  doi:10.7544/issn1000-1239.2015.20131918
Asbtract ( 749 )   HTML ( 0)   PDF (2695KB) ( 510 )  
Related Articles | Metrics
The numerical simulation of elasticity has been applied to many engineering fields such as architecture, machinery, chemical industry, material and spaceflight. With the increase in computation scale and precision of real-world applications, sequential algorithms are not able to satisfy applications' needs, especially for those with complicated CAD model and material. To alleviate this problem, we propose a parallel finite element algorithm based on hierarchical unstructured mesh, and apply it to elastic equations. Our algorithm consists of a novel unstructured mesh data structure obtained through hierarchical domain decomposition and a corresponding two-step algorithm for the stiff matrix of elasticity system. By comparing the results of a beam model with ANSYS, we validate the correctness of our algorithm. The results of steel tube model shows that our algorithm is able to solve problems with 1.5 billion cells and scale to 4080 processes.
Loop Tiling for Optimization of Locality and Parallelism
Liu Song, Wu Weiguo, Zhao Bo, Jiang Qing
2015, 52(5):  1160-1176.  doi:10.7544/issn1000-1239.2015.20131387
Asbtract ( 1557 )   HTML ( 7)   PDF (3660KB) ( 770 )  
Related Articles | Metrics
Loop tiling is a widely used loop transformation for exposing/exploiting parallelism and data locality in modern computer architecture. It is mainly divided into two categories: fixed and parameterized. These two types of tiling technologies are systematically summarized and their advantages and disadvantages are analyzed comprehensively. Since the tile size would significantly affect the performance of the tiled code, various methods of optimal tile size selection are described. Besides, various kinds of technologies applied to multi-level tiling, parallelism exploration and imperfectly nested loops are surveyed in this paper. Based on the detailed analysis of the current researches on loop tiling technologies, several conclusions are drawn as follows: 1) How to balance the trade-off between computation complexity and generation efficiency of tiled code has not been completely solved, and how to use loop boundaries to efficiently bound the iteration spaces for data locality enhancement also needs further study. 2) Optimal tile size selection is still a difficult and open question, and it would be significant to understand the influence of different level tile size in hierarchical memory system on performance. 3) From the perspective of application, how to automatically generate effective tiled code for arbitrarily nested loops needs further research. On the other hand, how to take full advantage of shared hierarchical memory and multi-core architectures to achieve high degree of parallelism for tiled code is another interesting direction.
Multiprocessor Hard Real-Time Systems Preemption Threshold Scheduling
Peng Hao, Han Jianghong, Lu Yang, Zhang Jianjun
2015, 52(5):  1177-1186.  doi:10.7544/issn1000-1239.2015.20140018
Asbtract ( 749 )   HTML ( 0)   PDF (2182KB) ( 570 )  
Related Articles | Metrics
The preemption plays a critical role in hard real-time systems. Preemptions are able to increase the schedulability of system. However, in multiprocessor platform, the large amount of preemptions may cause significant run-time cost due to context switch, running scheduler, job migration, etc. Besides quite amount of these preemptions are unnecessary regarding to schedulability. Limited preemption scheduling is the hybrid method between preemptive and non-preemptive scheduling, which can reduce unnecessary preemptions. In this paper, we extend the preemption threshold scheduling (PTS), one of the major methods of limited preemption scheduling, to multiprocessor hard real-time systems, which is firstly proposed for uniprocessor. The main focus of this paper is reducing preemptions. Based on DA-LC test, we derive the schedulability test for PTS. An efficient priority assignment algorithm OPA-MLL is proposed which is optimized for PTS from the combination of OPA and DA-LC. We also establish the threshold assignment algorithm aiming at reducing preemptions. The simulation result shows the PTS can reduce preemptions significantly for multiple priority assignment algorithms. At the meantime OPA-MLL has the largest percentage of schedulable task sets and most potential for reducing preemptions.
Adaptability of BFS Algorithm and Many-Core Processor
Ye Nan, Hao Ziyu, Zheng Fang, Xie Xianghui
2015, 52(5):  1187-1197.  doi:10.7544/issn1000-1239.2015.20140004
Asbtract ( 888 )   HTML ( 0)   PDF (2946KB) ( 540 )  
Related Articles | Metrics
Data-intensive applications represented by graph computing are getting more and more attentions, but traditional high performance computer is unable to solve the problems in the data-intensive applications efficiently. In order that future high performance computer architecture effectively support the data-intensive computing, this paper studies the features of graph algorithm represented by breadth-first search (BFS), as well as designs and implements a lightweight heuristic switch BFS algorithm. Through automatically switching between two different search methods, this algorithm avoids redundant memory accesses and improves search efficiency. Based on the discrete and random data access features of BFS algorithm and the execution mechanism of many-core processor, an analytical model of many-core processor architecture for BFS algorithm is established to the instruct the research on adaptability of BFS algorithm and many-core processor. The operating characteristics and performance trends of BFS algorithm are intensively studied on the typical many-core processors, and the results show that cache hit ratio, memory bandwidth, pipeline utilization efficiency and other related parameters are at a low level, which mean the current many-core processor architecture doesn't fully meet the demands of BFS algorithm. Therefore, new many-core processor architecture needs to be able to support a large of discrete random data accesses and a more easier execution mechanism.
Memory-Aware Incremental Mapping of Applications to MPSoC
Wang Yizhuo, Zuo Qi, Ji Weixing, Wang Xiaojun, Shi Feng
2015, 52(5):  1198-1209.  doi:10.7544/issn1000-1239.2015.20131960
Asbtract ( 670 )   HTML ( 0)   PDF (2941KB) ( 433 )  
Related Articles | Metrics
The modern multiprocessor system-on-chip (MPSoC) systems normally use network-on-chip (NoC) as their interconnection architecture. Application mapping is one of the key issues in the NoC-based MPSoC design. It maps the tasks of the applications to the nodes of the NoC topology. Many NoC-based MPSoC systems have a shared memory node to store data of the applications. For such MPSoC systems running multiple applications, a memory-aware incremental mapping strategy is proposed. In the strategy, memory access characteristics of the applications are obtained by offline analysis, which classify the applications into hot and non-hot applications. Then, different mapping algorithms are selected according to the memory access characteristic of an oncoming application at runtime. Hot applications are distributed as close as possible to the shared memory and the non-hot applications are distributed as far as possible from the shared memory, according to the proposed strategy. In addition, the application internal and external communication contents are minimized. Experimental results show that the proposed technique saves the communication energy cost by 34.6% on average, and increases the performance by as much as 36.3%, compared with the strategy using a greedy region selection and random mapping algorithms. Moreover, the proposed technique works well on different scale NoCs.
A Matrix-Indexed Bloom Filter for Flash-Based Key-Value Store
Li Wei, Zhang Dafang, Xie Kun, Li Wenwei, He Jie
2015, 52(5):  1210-1222.  doi:10.7544/issn1000-1239.2015.20131940
Asbtract ( 723 )   HTML ( 2)   PDF (3615KB) ( 466 )  
Related Articles | Metrics
Flash-based key-value store, an important type of NoSQL database, has been widely used to store and query data. Indexing structure is an effective organization of data in the store system, which is one of the key technologies to improve the performance of system insertion and query. On the analysis of the characteristics and shortcomings of current and relevant indexing structure, matrix-indexed Bloom filter (MIBF) for flash-based key-value store is proposed. MIBF is composed of multiple Bloom filter group (MBFG) represented by m×s bits matrix and additional Bloom filter (ABF). The core idea of MIBF is that flash page address of key-value pair is split into multiple bit groups, and MBFG is also divided into multiple groups correspondingly, and each group bits are represented by one group Bloom filter (BF) in MBFG, while the combined value of key and flash page address is inserted into ABF. When an element is queried according to the key, each BF group in MBFG generates a plurality of bit values and combines to generate the flash page address for the key-value pairs. In order to reduce pseudo flash page address generated by the MBFG due to false positive probability, pseudo flash page addresses are filtered out through the ABF, thereby achieving more accurate address location, reducing the number of flash access, and improving the system performance. Compared with previous work, the address location accuracy of MIBF query is improved and the access number of RAM and flash is decreased significantly, which greatly improves the performance of solid state disk (SSD) insertion and query.