Computer Science

Recent Advances in P2P Streaming with Network Coding

Computer Science. 2012, 39 (3): 1-8.

Abstract

PDF(836KB) ( 462 )

RelatedCitation | Metrics

P2P streaming is a promising media content distribution technology. Network coding can be adopted into a P2P streaming system to further improve its overall performance. Focused on currently popular data driven overlay network based P2P streaming system framework and based on two streaming modes, i. e.，live streaming and on-demand streaming,the implementation mechanisms,merits and drawbacks of the typical P2P streaming schemes using network coding were discussed in detail. At last, the open issues of this research direction were presented.

Survey of XQuery Implementation

Computer Science. 2012, 39 (3): 9-13.

Abstract

PDF(525KB) ( 403 )

RelatedCitation | Metrics

As increasing amounts of information arc stored, exchanged, and presented using XMI，the ability to query XML data sources becomes increasingly important in XML database field. The flexibility and complexity of XQuery language are the great challenge to XQuery implementation. High-performance implementation of XQuery needs to use query optimisation methods provided by XMI. query algebra, also needs to use efficient holistic twig matching algorithm. This paper presented a basic architecture of XQuery implementation, and then gave an overview of the current status of two key technology for native XQuery implementation-XMI. query algebra and tree pattern matching. Finally, this paper prospected future research directions and presented some viewpoints of XQuery implementation.

Tree Decomposition and its Applications in Algorithms:Survey

Computer Science. 2012, 39 (3): 14-18.

Abstract

PDF(418KB) ( 1182 )

RelatedCitation | Metrics

Tree width and tree decomposition arc two important concepts developed by graph minor theory. Because of its own characteristics, tree decomposition plays an important role in algorithm design. The tree width of graph, tree decomposition algorithm, applications of tree decomposition algorithm for problem solving in a complex problems were deeply analysed. Three aspects of the related research in recent years were given a thorough analysis and presentation,and a number of important principles and methods were presented by some simple examples. Furthermore, a few future research issues were outlined.

Research on Service Matching Method for LBS

Computer Science. 2012, 39 (3): 19-22.

Abstract

PDF(378KB) ( 449 )

RelatedCitation | Metrics

With the development of pervasive computing, location-based service is becoming an important aspect of applied research, and the technology of service discovery becomes a core issue. So service matching is the most important in service discovery, also it became hot spot in researching. In the process of providing service to user, not only the quafity of service should be improved, but also user's preferences should be considered. I}he existing mainstream service discowry protocols in the location-oriented service were compared. Based on analysis and comparison, a new algorithm of service matching was proposed. It improves the service matching success rate through hierarchical matching and full accounting of the user's preference, and ultimately aims to improve service quality.

Load Evaluation Method about Cloud Computing Cluster Based on the Load Grayscale Mapping Model

Computer Science. 2012, 39 (3): 23-27.

Abstract

PDF(429KB) ( 421 )

RelatedCitation | Metrics

To assess the overall load status of millions of nodes in cloud computer ctuickly, this paper constructed a mapping model that loads information map to grayscale image based on the entropy value and information theory. A conversion was completed from load balance to graphic ectualizer by analyzing the relationship. There are some experiments by using image compression, image entropy, haar wavelet to analyze image. A load evaluation method was proposed. The experiments show that this method can assess cluster balance quickly and thoroughly. A new load status value is provided for further study of load balancing algorithm.

Construction and Simulation of Worm Propagation Model in Vehicular Internet of Things

Computer Science. 2012, 39 (3): 28-32.

Abstract

PDF(537KB) ( 377 )

RelatedCitation | Metrics

In urban-road environment vehicular Internet of things vehicle nods draw over an omnirange and complex road conditions domain, the road environment has barrier, superimposed disturbance influence over wireless signal. Inosculating with the intelligent driver model, we investigated the outbreak of worm epidemics in vehicular Internet of things. Our study constructed a vehicular Internet of things worm propagation model with vital mean velocity and shadow-fading component This model preferably shows the influence over worm propagation in vehicular Internet of things by these components, and factually simulates the worm propagation in vehicular Internet of things, and provides a theoretical basis for programming real-time detection strategy and preventing worm destructive epidemics in vehicular Internet of things.

Resource Optimization for Uncertain Traffic in Multi-radio Wireless Networks

Computer Science. 2012, 39 (3): 33-38.

Abstract

PDF(549KB) ( 391 )

RelatedCitation | Metrics

Multi radio wireless network is one of the trends for future wireless network, which has the characteristics of multiple interfaces,multiple channels and multiple hop. The channels and links resource optimization in such network is a joint optimization problem of routing, channel allocation and link scheduling. In the existed related approaches, the network traffic is simply assumed to be deterministic and stable. However,it is known that there is always some uncertainty in real network traffic. In this paper, one joint optimization model for network throughput maximization was proposed under the constraints of transmission flows, channels and interferences. With the optimal solution with uncertain input traffic,one link schedule scheme was also proposed. Numeric simulation results show that our solution has better performance for uncertain traffic demand.

Area Division Based Semi-auto DV-Hop Localization Algorithm in WSN

Computer Science. 2012, 39 (3): 39-42.

Abstract

PDF(432KB) ( 414 )

RelatedCitation | Metrics

A lot of key problems need to be studied and solved in the field of WSN, and node self-localization is one of them. In numerous localization algorithms,DV-hop is popular with discussion or referenced localization algorithm,but it takes the results of hops multiplied by network average j umps as the actual distance between the nodes, while the accuracy of calculating the average every hop distance, the character of network, the node density, topology structure, etc are major factors which influence the positioning accuracy of DV-Hop algorithm. We put forward an improved DV-Hop algorithm,area division based semi auto DV-Hop localization algorithm (ADBSA DV-Hop). Several ideas were employed to improve DV-Hop, including semi-auto average size of per hop acquirement, area division, and sticking to border. ADBSA DV-Hop was simulated on MATLAI3 platform, to compare with DV-Hop. Experiment indictes that ADBSA DV Hop performs better than DV-Hop, and competently meets the localization rectuirement of sticking to border.

Adaptive Peer-to-Peer Overlay for the Maximum Throughput

Computer Science. 2012, 39 (3): 43-46.

Abstract

PDF(483KB) ( 435 )

RelatedCitation | Metrics

The intrinsic value of P2P system is to improve the utility ratio of system resources and the system throughput,as well as to satisfy more data requests. In many unstructured P2P systems,the peers with high popularity weight in the overlay arc assigned with more connections, so as to receive more messages and hit more requests and finally to improve the search success rate. Due to the lack consideration of bandwidth, the peers with high weight are apt to be overloaded and the available services decrease. Therefore, the high success rate alone doesn't mean the high throughput and service availability. An optimization solution of overlay network was proposed in this paper to improve the throughput and the number of access customers, in which the connections are adaptively adjusted according to the available bandwidth and the popularity weight. Our simulations show that our method can improve the system throughput as high as 22% with low cost.

ARIMA-based Weighted Clustering Algorithm for Prediction of Nodes' Location in Ad-hoc Network

Computer Science. 2012, 39 (3): 47-50.

Abstract

PDF(347KB) ( 471 )

RelatedCitation | Metrics

This paper introduced ARIMA prediction mechanism in weighted clustering algorithm (WCA). During routing maintaining process, the ARIMA is used to predict the network node location. Using the established ARIMA model, the algorithm is able to predict geographical position of the node at next time. In this way, it can calculate aggregate holding time of the nodes. Then, the predicted aggregate holding time is compared with time warning threshold, if clusto structure will be unstable, route recovery process will be activated before the link fails. And it will search new routing in order to avoid frequent link failures. Thus, the influence to the routing protocols brought by the dynamic changes of network topology can be reduced, and the stability of the cluster structure will be maintained. The simulation results show that, compared with LOWID and RLWCA not joined the forecasting mechanism, the proposed ARP-LWCA algorithm can dramatically improve the network packet delivery rate,reduce the network normalized overhead and the number of routing interruptions significantly. So, the network performance is improved.

Research on BIC Security Mechanisms of the Polymorphic Key Exchange Protocol

Computer Science. 2012, 39 (3): 51-53.

Abstract

PDF(261KB) ( 464 )

RelatedCitation | Metrics

DifficHcllman key exchange algorithm, which is used in regular scenes based on the discrete logarithm problem, demands that both of two communication parties struck up a lively conversation long-term dependable fellowship. A much more secure polymorphic key exchange algorithm was proposed based on the DifficHellman key exchange algorithm The identity information of two parties can be appended to the agreement. Both communication parties use their PRNGs to finish the polymorphic virtual S-box together. The polymorphic S-box can become a broad agreement in irregular scenes.

Modeling the Subjective Dynamic Trust with Behavior-based Attestation

Computer Science. 2012, 39 (3): 54-61.

Abstract

PDF(729KB) ( 410 )

RelatedCitation | Metrics

In a distributed computing environment how to establish a trust relationship between entities has been a hot issues for information security, and remote attestation provides a new research direction for solving the issues. Remote attestation is an important feature of trusted computing, and entities can establish trust relationship by using the remote attestation. However, some static remote attestation methods such as binary based attestation arc obviously inadequate to attest the trustworthiness of computing platform. They don't provide sufficient evidence in establishing trust relationship. Therefore, this paper used behavior-based attestation method to prove the trustworthiness of computing platform. This method can provide more accurate empirical results for establishing trust relationship. In additional, there are some uncertainties in behavior-based attestation, and these uncertainties will affect the establishment and evaluation of trust relationship. This paper used subjective logic to measure the trust relationship and build the dynamic trust model TMBA. This model can analyse dynamics of trust relationship by considering the past and present empirical results which arc collected from behavior-based attestation, and represent the trust degree with the trust point in subjective logic. Finally, the method for calculation of the trust point was given.

Provable Secure Route Optimization Scheme for HMIPv6 in Wireless Mesh Network

Computer Science. 2012, 39 (3): 62-66.

Abstract

PDF(398KB) ( 363 )

RelatedCitation | Metrics

HMIPv6 technology can implement the seamless handover in wireless mesh network. ho address the security issues of route optimization in the mobile handover binding update procedure,a elliptic curve cryptography self-certified public key cryptosystem based secure route optimization scheme was proposed, which is applicable to the wireless mesh network. hhe proposed scheme not only addresses authentication and authorization of binding update messages in route optimization for mesh clients, but also provides security for the binding update messages by effective session-key negotianon mechanism, which affords provable security. Furthermore, the performance analysis shows that the proposed scheme can simplify the procedure of standard routing optimization scheme and improve the efficiency of the general registration procedure.

.Ioint Detection of Difference Value Energy for Spectrum Sensing in Cognitive Radio

Computer Science. 2012, 39 (3): 67-70.

Abstract

PDF(344KB) ( 459 )

RelatedCitation | Metrics

In cognitive radio systems, cognitive users require a accurate and real-time judgment of the busy or free of the spectrum. But it is usually very difficult if the cognitive user stations in severe fading or interference. According to these facts,we proposed to use statistical difference value of the primary user and the noise to revise the energy detection.Then we further used cyclostationay detection in the confused area to get more reliable result. The final result is based on the joint judgment of the both detection. Simulation result shows that the proposed method excels energy detection in higher reliability, and cyclostationary detection in lower computation. It presents accurate real-time detection performanc'e even when the noise is in major fluctuation.

Research on Intrusion Detection System Based on Commodity Multi-core Platform

Computer Science. 2012, 39 (3): 71-74.

Abstract

PDF(333KB) ( 573 )

RelatedCitation | Metrics

To deal with the rapid increment of network traffic,an Intrusion Detection System (IDS) based on commodity multi-core platform was proposed. This paper evaluated some critical factors for the system performance, such as hardware,resource-assigning and network traffic features. Extensive experiments demonstrate that number of traffic flow and pps index have larger impact on system performance. I}he ids performance can be improved obviously by actieating the Hyper-Threading of multi-core processor and binding the detection engine with the CPU core. Our system is easy to be realized and has low priccperformancc ratio.

Analysis and Verification of Secure E-commerce Payment Protocol Based on Four Parties

Computer Science. 2012, 39 (3): 75-78.

Abstract

PDF(411KB) ( 428 )

RelatedCitation | Metrics

Both the finite state model and the CTL (Computation Tree Logic) formulations were first constructed for the secure e-commerce payment protocol based on four parties (FSE7)in this paper. Then, the symbolic model checking (SMV) was used to analyze and verify the atomicity of the FSET protocol. I}he result of analysis and verification indicafes that the FSET can meet with the money atomicity, the goods atomicity and the certified delivery, as well as the elegy tromc payment security requmements.

Access Control Algorithm with Buffering in Cognitive Radio System

Computer Science. 2012, 39 (3): 79-82.

Abstract

PDF(315KB) ( 392 )

RelatedCitation | Metrics

We built and analyzed the model of the cognitive radio system with buffering by continuous time Markov.Aimed at the character that the access of overmany users will result in the forced termination of the service, we designed an algorithm to control access probability of the cognitive users, which maximizes system throughput in the precondition of satisfying the forced termination limitation. The simulation result shows that, in the system using the algorithm, the user access probability and system throughput increase with the forced termination limitation. Also the largest access probability under the forced termination limitation is the access probability which can maximize the system throughput.The system satisfies the forced termination limitation at the sacrifice of throughput At the same time, the simulation indicates that the introduction of buffering can improve the user access probability and the system throughput performance.

Fast Approximation Algorithm Based on Adjacent Matrix for Construction Virtual Backbone

Computer Science. 2012, 39 (3): 83-87.

Abstract

PDF(405KB) ( 363 )

RelatedCitation | Metrics

In Ad-hoc networks, a minimum connected dominating set (MCDS) can be used as a virtual backbone to improve the performance of source allocation and prolong the system lifetime. In this paper, we firstly proved a useful theorem about adjacent matrix Secondly, using the theorem and the relationship between maximum independent set and minimum dominating set,we proposed a fast approximation algorithm based on adjacent matrix for constructing MCDS in Ad-hoc networks. hhe correctness, complexity and approximation rate of the proposed algorithm were analyzed respectively. Simulation results show that new algorithm can efficiently and fast construct virtual backbone in Ad-hoc networks.

Reducing Number of Free Riders in Trust Model

Computer Science. 2012, 39 (3): 88-92.

Abstract

PDF(403KB) ( 388 )

RelatedCitation | Metrics

Although current existing trust model reduces the impact of peers' malicious attack in P2P system, these repir tation systems do not concern with reducing free riders in P2P networks,namely,peers with high trust value tansform to free riders. Because lots of free riders exist, robust and avaliable of P2P system arc degraded. So, a trust model based on time slots was designed,and the nearer time from now the greater time slot's weight was gaven. Theoretical analysis and simulation show that this proposal not only prevents peers with high trust value to free riders, but also limits peers to make malicious attack recently, and peers' trust value arc more and more bight in compared with other proposals.

Algorithms for Dominating Set Problems in OTIS Networks

Computer Science. 2012, 39 (3): 93-97.

Abstract

PDF(404KB) ( 461 )

RelatedCitation | Metrics

The minimum dominating set problem and the minimum connected dominating set problem, both of which are NP-hard problems, have many important applications in the fields related to networks and parallel&distributed computing. Recent OhIS networks arc a class of two-levcl structure interconnection networks taking any graph as modules and connecting them in a complete graph manner, which provides a systematic competitive construction scheme for large,scalable, modular, and robust parallel architectures while maintaining favorable properties of their factor networks. In this paper, how to construct a small dominating set and connected dominating set of an OhIS network was discussed. Based on the connectivity rule of OTIS networks,we gave algorithms for constructing a small dominating set (a small connected dominating set, respectively) of an O`hIS network from a dominating set (a connected dominating set, respeclively) of its factor network. The performances of these algorithms were analyzed, and were shown by examples.

Power Allocation with Hybrid Protection Criterion for NC-OFDM-based Cognitive Radio System

Computer Science. 2012, 39 (3): 98-100.

Abstract

PDF(242KB) ( 362 )

RelatedCitation | Metrics

This paper investigated power allocation algorithms for NC-OFDM based cognitive radio system, which access the spectrum originally licensed to an OFDM primary system. According to transfer status of primary users, there will be different constraint strategies:A new criterion referred to power leakage interference factor is proposed to constraint leakage power to primary users in the cognitive users’working channels; meanwhile, on the primary users’working channels, primary users are protected by keeping the interference introduced to primary users' rate loss below a threshold. Power allocation algorithm maximizes the rate of the cognitive radio system based on the hybrid constraint strategics. hhen the numerical result show that, compared with the conventional interference power constraint, the cognitive system can achieve a significant rate gain under the proposed constraint.

Core Functions Analysis and Example Deployment of Virtual Honeynet

Computer Science. 2012, 39 (3): 101-103.

Abstract

PDF(351KB) ( 513 )

RelatedCitation | Metrics

As conventional honeynet's low hardware utilization, complex configuration and difficult management arc increasingly appearing,how to solve these problems has been getting more and more researcher's attention. Aiming at the problems that honeynet currently is facing, the paper proposed the necessity of using virtual technology to construct honcynet. Through the studying on core functions of honcynet, the paper analyzed and provided the workflow of core func- lions in virtual systerm. Based on that, we designed and implemented a proposal of the virtual honeynet.The results show that the established virtual honcynet works well and solves the shortcomings of conventional honcynet in a certain extent.

Study on GSNPP Algorithm Based Privacy-preserving Approach in Social Networks

Computer Science. 2012, 39 (3): 104-106.

Abstract

PDF(233KB) ( 389 )

RelatedCitation | Metrics

With the rapid development of network information technology, social networks have sprung up. For the protection of their privacy, we proposed a GSNPP algorithnrbased privacy-preserving approach. By clustering the nodes in social networks,and then making generalization not only within cluster but also among clusters,the approach processes the social networks anonymously, to achieve the purpose of privacy protection, then quantifies the information loss of different types in the process of the anonymity of social networks. At last, the results of experiment demonstrate the feasibility and validity of the approach.

Evaluation of Hop-distance Relationship for Sensor Networks in Internet of Things

Computer Science. 2012, 39 (3): 107-109.

Abstract

PDF(241KB) ( 394 )

RelatedCitation | Metrics

This paper presented an analytical method to evaluate the hop-distance relationship for wireless sensor network in a shadow fading envirorunent,where sensor nodes are randomly and independently deployed in a circular region by a Poisson process. Different from the UDG model, the shadow fading model has the non-uniformity property for connectivity. We derived an approximate recursive expression of the probability of the hop count by a given geographic dislance. The multi-hop dependence problem was also taken into consideration. Furthermore, we gave the expressions about the distribution of distance by a known hop count by the Bayer formula .The simulation results show that the analytical expressions can closely agree with the statistical data and the border effects cannot be ignored.

Research on Server Centric Data Center Network Design

YIN Dong,MU De-jun,DAI Guan-zhong

Computer Science. 2012, 39 (3): 110-112.

Abstract

PDF(332KB) ( 358 )

RelatedCitation | Metrics

Data centers are becoming increasingly important infrastructures for many essential applications such as data intcnsivc computing and largcscalc network scrviccs. According to the previous rcscarchcs, this paper prcscntcd a high1y scalable cylinder data center interconnection architecture, with a simple yet efficient routing scheme that maintains short path length in servers communications. It proposed fault tolerant and traffi}aware routing schemes to ensure balanccd load. Experiments were used to test the transmission and routing performance of the design. Also,fault tolerance and load balance were evaluated.

Fault-tolerant Routing Algorithm in 2D-Mesh

XU Da-cheng,FAN Jian-xi,ZHANG Shu-kui

Computer Science. 2012, 39 (3): 113-117.

Abstract

PDF(494KB) ( 628 )

RelatedCitation | Metrics

A fault tolerant routing algorithm for 2I}Mesh that uses only two virtual channels was presented. Previous1y, l3oppana needs 4 virtual channels, and Duan needs 3 virtual channels. The algorithm is based on the block fault model.The fault region can be f-ring and f-chain at the same time. Shortest paths are used for routing if there are no faults, while detour paths are used for blocked messages. We have proved that our algorithm is deadlock-free under the non-overlapping and overlapping situation.

Automatic Generation of Attach-based Signature

WANG Guo-dong,CHEN Ping,MAO Bing,XIE Li

Computer Science. 2012, 39 (3): 118-123.

Abstract

PDF(487KB) ( 380 )

RelatedCitation | Metrics

Signatures can be generated based on characteristics of attacks. Using dynamic program analyzing skills we generated binary signatures for control flow attack to return value of function call and function call pointer, and noncontrol flow attack to decision-related variable. First, we identified instructions related to the vulnerability. Second, we monitored these instructions using a modified virtual machine. At last, we alerted and generated signature after finding any malicious write behaviors. Patch recorded malicious write instructions could be generated meanwhile to ignore these instructions in future execution. Generated signature could be sent to other computers to monitor the same software's execution using lightweight virtual machine. Experiment results show that binary level signature has simplified form and precise functionality and low false negative and is effective to defense polymorphic attack. Besides, lightweight virtual machine makes use of the signature fast.

FILiC:A Framework for Interactive Library on CUDA

WU Wei,QING Peng,QI Feng-bin

Computer Science. 2012, 39 (3): 124-127.

Abstract

PDF(454KB) ( 500 )

RelatedCitation | Metrics

NVIDIA developed the CUDA programming model which provides a way to accelerate more general applicalions by GPU. But CUI)、threads cann't access peripherals directly. As far as library functions interacting with peripherals, only‘printf' is allowed in CUDAthreads by now. We described a framework named FILiC for interactive library,which implements I/O functions in CUDA threads efficiently by interactions between the device and the host And FILiC is a framework with good scalability一CUDA progammers and compiler developers can use it to design some new library functions which interact with peripherals for CUDA threads.

Safety-centered Architecture Design Method for IMA Software

XU Xian-liang,ZHANG Feng-ming,CHU Wen-kui

Computer Science. 2012, 39 (3): 128-130.

Abstract

PDF(364KB) ( 398 )

RelatedCitation | Metrics

Based on adaptation of architecture tradeoff analysis method (ADAM)，a safety-centered architecture design method was proposed for integrated modular avionics (IMA) software. Hazardous scenarios were used to evaluate the safety property of a designed IMA software architecture. Prevention, elimination or minimization actions to fateful hazards were derived. Contracts were used to document all the constraints which should be met in the next refined process of IMA software architecture. With the method, it will eliminate or reduce design bugs in the IMA software architecture, especially those that will contribute to hazards of the IMA system or fighters.

Data Flow Analysis Based on the Variable Scope

JIANG Shu-Juan,ZHAO Xue-feng

Computer Science. 2012, 39 (3): 131-134.

Abstract

PDF(288KB) ( 386 )

RelatedCitation | Metrics

As an important technology of programming analysis, data flow analysis is widely applied into kinds of software projects. Problem of variables being hidden and covered for their scope has not been taken into accout in traditional dataflow iteration analysis,leading to inaccurate data flow information. An improved dataflow analysis method based on variables scope and traditional dataflow iteration analysis method was proposed to solve the problem of varibles being hidden and covered. At last, both of these methods were applied into program slice, which proves the efficiency of the improved one by comparing.

Linear Linklist Based Algorithm for Fuzzy Association Rule Mining

LIU Qing-bao,WANG Wen-xi,WANG Wan-jun

Computer Science. 2012, 39 (3): 135-138.

Abstract

PDF(385KB) ( 375 )

RelatedCitation | Metrics

In order to improve the efficiency of existing fuzzy association rule mining algorithms, we presented a linear linklist based algorithm for fuzzy association rule mining. Utilizing the linear hnklist our algorithm only records the information of the tran-suctions which arc useful for counting the support of the frequent itemset, and simplifies the transuctions information according to the previous results,which reduces the cost of data storage and increases the running efficiency. Experiments demonstrate that our method is efficient in fuzzy association rule mining.

Adaptive Method to Select Policy in HSM

HU Na ,LI Zhan-huai,ZHANG Xiao

Computer Science. 2012, 39 (3): 139-143.

Abstract

PDF(436KB) ( 436 )

RelatedCitation | Metrics

In the hierarchical storage management (HSM)，it is difficult to choose a data migration policy which meets precisely the diverse and the changes in business data access patterns, so that the concept of policy priority could help to quickly choose the most appropriate policy for the HSM system. The value of a policy priority is dynamically adjusted before and after a migration which is driven by the policy, and then, the HSM system chooses the policy that has highest priority value as the policy for the next migration. After a few adjustments like this, the system will obtain the optimal policy. The prototype experiments show that the method can indeed adaptively choose the best policy by dynamically adjusting the priority, therefore, the impact on the business applications is greatly reduced.

X-Hop; Storage of Transitive Closure and Efficient Query Process

SHU Hu,CHONG Zhi-hong ,NI Wei-wei ,LU Shan ,XU Li-zhen

Computer Science. 2012, 39 (3): 149-152.

Abstract

PDF(463KB) ( 454 )

RelatedCitation | Metrics

Reachability query is one of the fundamental problems of management of massive directed graphs. This paper considered reachabihty query under the context of dense graphs. We proposed a storage schema, called X-Hop, which compresses the storage of 2-Hop via a multipl}hop schema. By organizing center vertexes in a tree structure, X-Hop storage delivers efficient query process in addition to high compression ratio. Extensive experiments demonstrate the efficiency of our proposal.

Algorithm of Frequent Patterns Finding Based on Large Scale Corpus Partition

DING Xi-yuan,HUANG He-yan,ZHANG Hai-jun,WANG Shu-mei

Computer Science. 2012, 39 (3): 153-156.

Abstract

PDF(422KB) ( 458 )

RelatedCitation | Metrics

Frequent patterns finding is useful for some areas, such as new word recognition, Internet public opinion monitoring, bio-information series detection, etc. Considering that corpus size is much larger than memory capacity, we put forward a pragmatic algorithm to find frectuent patterns. Firstly, corpus was partitioned into multiple sets based on first character of suffix,and then a concept of maximized longest common prefix interval (MLCPI) was introduced,and by means of searching it while scanning data in sets item by item, we accomplished the finding task. Besides, we proposed hierarchical reduction algorithm (HRA) to reduce sulrstring during the finding process on that basis. There is no need to import all data into memory, so it will decrease resource consumption. Moreover, it is found that frequent patterns among sets do not interfere with each other, which will improve the speed while processing paralleled. We used 4. 61 gigabytes plain text as experiment data. The results show that the memory usage is lower than 30 megabytes, and the speed is up to 1. 08 megabytes per seconds, and it is able to reduce sub-string efficiently.

Research of Ranking Algorithm Based on Information Quantity and Entropy in Meta Search Engine

LAI Xiang-xu,HAN Li-xin,ZENG Xiao-qin,WANG Min,WU Sheng-li

Computer Science. 2012, 39 (3): 157-159.

Abstract

PDF(380KB) ( 344 )

RelatedCitation | Metrics

The meta search engine collects results from many search engines, using a certain way to treat the results and then returning back to the users. Reranking the results will directly affect the performance of meta search engine. This paper was based on information quantity and entropy which arc used in communication field then presented a calculation algorithm-information related degree(IRD),after a particular amendment to the IRl)algorithm, this paper also pro- posed a merging algorithm combMul. The above algorithms were applied to the meta search engine, and MRR precision was used to evaluate the algorithm .The MRR precision data show that IRD algorithm is even better compared with a widely used sorting algorithm-Borda.

Cluster Algorithm for Time Series Based on Key Points

XIE Fu-ding,LI Ying,SUN Yan,ZHANG Yong

Computer Science. 2012, 39 (3): 160-162.

Abstract

PDF(344KB) ( 696 )

RelatedCitation | Metrics

Based on key point technology, a new method for time series cluster was proposed. hhe key points for each time series were first found, and then the complex network was constructed by calculating the similarity between key point series after they were ectuidimensional. At last, the clustering time series were implemented by partitioning the complex network into communities. hhe experimental results show that the dimensions of time series and the consumplion of computing time can be effectively reduced by the proposal. Furthermore, the desired cluster result is obtained when applying this method to cluster some practical data.

Research on Privacy Preserving Distributed Clustering Algorithm

LIU Ying-hua,YANG Bing-ru,CAO Dan-yang,MA Nan

Computer Science. 2012, 39 (3): 163-169.

Abstract

PDF(243KB) ( 358 )

RelatedCitation | Metrics

Privacy preserving data mining is to discover accurate rules and knowledge without precise access to the raw data. I}his paper focused on privacy preserving clustering algorithms mining in a distributed environment, and presented a fully homomorphic encryption algorithm based on distributed k-means (FHE-DK-MEANS algorithm). Theoretical analysis and experimental results show that FHE-DK-MEANS algorithm can provide better privacy and accuracy.

Clustering-based Algorithms to Semantic Summarizing the Table with Multi-attributes' Hierarchical Structures

SUN Chong, LU Yan-sheng

Computer Science. 2012, 39 (3): 170-173.

Abstract

PDF(632KB) ( 347 )

RelatedCitation | Metrics

Table semantic summarization is to create a small size summary table by using a few general tuples to replaceall tuples in the raw data table with the help of attributes' concept hierarchies. I}he aim of summarisation is to restrict the size of the summary table to a fixed value with the semantic information remained in it as more as possible. The existing method translates table summarization to a set covering problem and spends much cost in the problem translation which makes it impractical. We defined the metric space of tuples with multi attributes’hierarchical structure and translated this problem to a clustering problem in a hierarchial space. We proposed two algorithms. One was hierarchial agglomerative method and the other was based on the idea of adjusting the resolution of the hierarchial space. The experiment on real life dataset shows that our methods arc better than the existing one in both running time and summary quality.

Tuning of Parallel Frequent Pattern Growth Algorithm Based on Distributed Coordination System

WANG Jie,DAI Qing-hao,LI Huan

Computer Science. 2012, 39 (3): 174-182.

Abstract

PDF(354KB) ( 394 )

RelatedCitation | Metrics

Frequent pattern mining can find frequent pattern in data, and iYs an important step in the association rules mining. Parallel frequent pattern(PFP) algorithms apply it into parallel environment, which is suitable for massive data.Based on the implementation of Apache Mahout, this paper proposed a design for optimizing the counting and sorting parts of PFP using distributed coordination system. This design takes advantage of distributed coordination system and reduces the consumption on HDFS and memory of data node. Another benefit is that the counting procedure and sorting procedure start parallclly. At last this paper analyzed the experimental result and the difficulties for implementation for further study.

Extracting Abbreviated Names for Chinese Entities from the Web

DING Yuan-jun,CAO Cun-gen,WANG Shi,FU Jian-hui

Computer Science. 2012, 39 (3): 183-186.

Abstract

PDF(827KB) ( 424 )

RelatedCitation | Metrics

Abbreviations arc the essential parts of the vocabularies in natural language, therefore, acquiring abbrevia- dons is a basic and significant task of natural language processing. We proposed a method of extracting abbreviations for the given Chinese full names from the Web. The method has two phases: candidate abbreviations extraction and verifica- tion. In the extraction phase, we constructed query items to issue to Google and saved the results as the corpora, from which we extracted candidate abbreviations. In the verification phase, we defined a full names/abbreviations relations constraints, which includes a group of constraint axioms and a group of constraint functions. We built a relation graph to reflect the connection of all the full names and the abbreviations. In the process of verifying, the incorrect ones could be filtered out using the constraint axioms and the relation graph; the candidate abbreviations could be classified with the constraint functions,and the incorrect ones could be identified through a classifier,which was trained using the types of the candidate abbreviations, the values of the functions and the tags in the corpora. Comprehensive experiments show that the precision and recall rate of extracting abbreviation extraction arc 94. 63 0 0 and 84. 09%，respectively, and the precision of candidate verification is 94. 81%.

Parallel Computing and Rendering Framework of Time Variable 3D Scalar Fields

YU Rong-huanl,DENG Bao-song,WU I,ing-da,QU Shi

Computer Science. 2012, 39 (3): 187-191.

Abstract

PDF(452KB) ( 385 )

RelatedCitation | Metrics

According to the characters of time variable 3D scalar fields, a parallel computing and parallel rendering framework combining sort-first and sort: last parallel rendering method was proposed. This framework adopts scene task distribution in parallel computing step and adopts screen distribution in parallel rendering step. The experiments show that this framework can effectively improve the stability and capability of the parallel computing and rendering.

Method of Structure and Fusion for Uncertainty Seminar Information

XIANG Dong,ZHAO Yong,CHEN Yang

Computer Science. 2012, 39 (3): 192-195.

Abstract

PDF(411KB) ( 362 )

RelatedCitation | Metrics

In group discussion, because the thinking of experts is uncertainty and information is unstructured, group discussion is difficult to reach consensus. To solve this problem, this article gives a information model which is composited of natural and artificial property. Mechanism of how to extract uncertainty information is studied with argument frame- work,valid arguments group and distribution function. A method is discussed,which is information fusion based on a- verage argument. All is to promote awareness of the spiral and groups to reach consensus. Finally, a case is provided to prove feasibility and effectiveness of model and method,which is discussion about customer's demand of car.

Document Classification Algorithm Based on Manifold Regularization

XU Hai-rui,ZHANG Wen-sheng,WU Shuang

Computer Science. 2012, 39 (3): 196-199.

Abstract

PDF(349KB) ( 376 )

RelatedCitation | Metrics

A novel document classification algorithm based on manifold regularization framework, which is called MI_I} RLSC, is presented to resolve high dimensional document classification. In the proposed MLI}RLSC, a nearest neighbor graph was constructed and the intrinsic geometrical structure of the sample space was taken as a manifold regularization term,then it was incorporated into the objective function of the multivariate linear regression to extract lower dimen- sional space. The classification and predication in the lower dimensional feature space are implemented with kNN. Ai- ming to extract effective features for the multi-class problem, MLD-RLSC can make use of all labeled samples. Experi- mental results on Reuters 21578 dataset demonstrate that the proposed algorithm is of higher classification accuracy and faster running speed.

Improvement of Web Information Extraction Based on Genetic Algorithm and Hidden Markov Model

LI Rongl,HU Zhi-jun,ZHENG Jia-heng

Computer Science. 2012, 39 (3): 200-205.

Abstract

PDF(443KB) ( 521 )

RelatedCitation | Metrics

In order to further enhance the accuracy and efficiency of Web information extraction,for the shortcomings of hybrid method of genetic algorithm and first order hidden Markov model in the initial value selection and parameter op- timization, an improved combined method embedded with genetic algorithm and second-order hidden Markov model was presented. In the hierarchical preprocessing phase, text was segmented hierarchically into proper lines, blocks and words by using the format information and text features. And then the embedded genetic algorithm and second-order hidden Markov hybrid model were adopted to train parameters, and the optimal and sulroptimal chromosomes were all retained to modify initial parameters of I3aum-Welch algorithm and genetic algorithm was used repeatedly to fine-tune the se- cond-order hidden Markov model. Finally the improved Viterbi algorithm was used to extract Web information. Experi- mental results show that the new method improves the performance in precision, recall and time.

Generalized Intuitionistic Fuzzy Implication and its Residuated Lattice

XUE Zhan-ao,XIAO Yun-hua,CHENG Hui-ru,XUE Hai-feng

Computer Science. 2012, 39 (3): 206-208.

Abstract

PDF(354KB) ( 386 )

RelatedCitation | Metrics

Intuitionistic fuzzy implication plays an important role in the intuitionistic fuzzy reasoning, and provides basic theory for applications of the uncertain reasoning and decision-making. hhc instuitionistic fuzzy implication was rc- searched. The basic knowledge of the intuitionistic fuzzy was firstly reviewed, a new kind of the generalized intuitionistic fuzzy implication was constructed, and its properties were proved, such as its monotonicity law and boundary, etc. Fur- thcrmorc, it was proved that the implication can construct the intuitionistic fuzzy rcsiduatcd lattice.

Parallel Traffic Signal Numerical Optimization Algorithm Study

ZHANG Li-dong,JIA Lei,ZHU Wen-xing,SHI Xiao-wei

Computer Science. 2012, 39 (3): 209-211.

Abstract

PDF(247KB) ( 444 )

RelatedCitation | Metrics

Traffic signal optimization is based on the dynamic fluctuation of traffic flow,which is a best way to decrease traffic delay and increase traffic efficiency. In order to cost less time during optimization simulation, we presented a kind of parallel traffic signal numerical algorithm. hhis algorithm first defines the time intervals of traffic signal timings from the experience of traffic engineering experts and managers, then lists the feasible groups of time setting with the given interval p,and dismisses each plan to according computing node. After the node finishes its simulation task, the main node will accumulate the simulation report. The simulation with Paramics shows that, with our four computing nodes in the parallel network, the speedup ratio is 1. 75，and the simulation is greatly improved, also the optimal plan is selected quickly.

Application of QPSO Algorithm and Correlation Analysis in Feature Selection from ECG Signal

CAO Jun,LIU Guam-yuan,LAI Xiang-wei

Computer Science. 2012, 39 (3): 212-215.

Abstract

PDF(321KB) ( 322 )

RelatedCitation | Metrics

This paper discussed the feature selection from ECG signal in affective recognition. At first, the original fcatures with high correlation were deleted to reduce dimensionality of original feature set by correlation analysis. Andthen, an improved quantum-behaved particle swarm optimization with binary encoding algorithm was proposed to achieve effective feature selection in the feature space with reduced dimension. hhe experimental results shows that the affective recognition system based on this algorithm and fisher classifier recognize the anger,disgust,fear,grief,joy and surpnse successfully.

Situation-driven Framework for Context-aware Computing

Computer Science. 2012, 39 (3): 216-222.

Abstract

PDF(551KB) ( 435 )

RelatedCitation | Metrics

Context aware systems generally use contexts to drive higher applications. Because context information is di- verse in types and values,the systems developed are poor in extensibility and stability. This paper proposed a situation- driven model for context awareness computing. The framework is based on situation information, and it can shield the heterogeneity and diversity of original context information. Situation-recognition is the kernel of this framework. The situation is recognized from basic context information,and is used to drive related applications. This framework simpli- fies the processing on designing a system, and is helpful in improving the systems' extensibility and stability. The mech- anism of situation recognition based on neural network avoids the problem of knowledge explosion when it uses the mechanism of reasoning. A prototype system was implemented, and it validated the proposed infrastructure.

Research on Dynamic Obstacle Avoidance and Path

Computer Science. 2012, 39 (3): 223-227.

Abstract

PDF(450KB) ( 600 )

RelatedCitation | Metrics

Aiming at the problem of obstacle avoidance for mobile robot with the platform of ASR mobile robot, a novel approach based on behavior for dynamic obstacle avoidance was put forward, which divides the robot behavior during the entire run into four behaviors, including tendency to target behaviors, obstacle avoidance behavior, going along the wall and emergency obstacle avoidance behavior of four acts, including obstacle avoidance behavior. A multi-sensor- based autonomous mobile robot obstacle avoidance mechanism was designed. A recursive median filter-based method was proposed to avoid crosstalk by grouping sampling or interval sampling technologys. The data was improved in both space and time continuity. I}he ultrasonic signal crosstalk and other interference random signals were effectively re- duced. Experiments based on both simulation platform and ASR robot verified the effectiveness of the proposed approach.

LS-Pre; Forecast the Learners' Learning Styles Adaptively in an Open Learning Environment

Computer Science. 2012, 39 (3): 228-230.

Abstract

PDF(394KB) ( 436 )

RelatedCitation | Metrics

Learners always have their learning style preferences according to their different cognitive processes. Auto- matically modeling the learners' learning style can get the more accurate information compared with the questionnaires which is free from the problem of inaccurate self-conceptions of the learners. There are many problems in the current LS detecting methods, like only can detect the I_S dimensions in a specific model, can not adaptively adjust the I_S prefer- ences in a different learning environment. We provided a new method to forecast the learners' LSs which is called LS- Pre. In LS-Pre, non-linear dynamic programming is used to construct the mathematic model while simulated annealing algorithm is used to optimize the goal function. We illustrated the effectiveness of I_S-Pre in part 4 of this paper.

Chaotic Artificial Glowworm Swarm Optimization Algorithm with Mating Behavior

Computer Science. 2012, 39 (3): 231-235.

Abstract

PDF(308KB) ( 373 )

RelatedCitation | Metrics

According to basic glowworm optimization

Logical Framework for Evaluation of Multiple-premise

Computer Science. 2012, 39 (3): 236-243.

Abstract

PDF(644KB) ( 365 )

RelatedCitation | Metrics

The multi-premise problem is an important research field of decision making and its optimal decision reflects the state of the art research of decision theory. Many methods can achieve it in multi-premise decision making, and each method has its own difficulties. This paper first introduced a new concept premise set, proposed an algorithm to decom- pose premise set into the simplest form, and proved that the algorithm outputs minimal, non-complete premise sets for any given goal. Next the credibility of each premise was defined for measuring the difficulty of premise set, and the opti- mal premise set was recommended for the goal. Then this paper gave a formal description of the logical framework()for evaluation of multiple-premise,and proved its computability and reasoning faculty. Finally,a prototype of framework O was implemented in Prolog and its soundness was proved via experiments and application in software engineering.

Image Denosing Based on Context Model in Contourlet Domain

刘镇弢，李涛，杜慧敏，韩俊刚

Computer Science. 2012, 39 (3): 244-245.

Abstract

PDF(272KB) ( 354 )

RelatedCitation | Metrics

This paper presented an image denoising algorithm based on context model by analyzing distribution features of contourlets coefficients. I}he key of the proposed arithmetic is that through the analysis of C T coefficients distribution characteristics,we chose the appropriate denoising thresholding,adopted the context model to construct CI} coefficient's classification model,and according to different classification,image noise was removed by using different threshold. The experimental results show that the proposed algorithm can effectively remove the noise in images. The algorithm also demonstrates good performance in enhancing image PSNR and improves the image subjective visual impression.

Image Segmentation of Multilevel Thresholding Based on Spectral Clustering

Computer Science. 2012, 39 (3): 246-248.

Abstract

PDF(582KB) ( 344 )

RelatedCitation | Metrics

The thresholding is an important form of image segmentation and is used in many applications that involve image processing and object recognition. hhus, it is crucial to how to acquire a threshold of image segmentation. A novelmultilevel thresholding algorithm was presented in order to improve image segmentation performance at lower computational cost. hhe proposed algorithm determines the thresholdings by spectral clustering algorithm called Dcut that uses a new similarity function. hhe weight matrices used in evaluating the graph cuts arc based on the gray levels of an image, rather than the commonly used image pixels. For most images, the number of gray levels is much smaller than the number of pixels. Therefore, proposed algorithm occupies much smaller storage space and requires much lower com- putational costs and implementation complexity than other graph-based image segmentation algorithms. A large number of examples were presented to show the superior performance by using the proposed multilevel thrcsholding algorithm compared to existing thresholding algorithms.

Multispectral and Panchromatic Images Fusion Based on Directionlets

Computer Science. 2012, 39 (3): 249-250.

Abstract

PDF(266KB) ( 347 )

RelatedCitation | Metrics

The directionlets based on digital segments and integer grids theory can not only inherit the characteristics of dimension-dependable wavelets, but also obtain the flexible multi directional characteristic by changing the directions of transform and sequences. A novel fusion method for panchromatic and multispectral images based on directionlets trans- form(DT) and PCA was presented. Firstly,a linear principle component analysis(PCA) was performed on the multi- spectral images to extract its first principle component, then we used DT to extract the spatial detail information of high-resolution panchromatic image. Therefore, the fused image can carry more spatial and spectral information. Experi- mental results show the new fusion method has a better performance, such as universal image quality index(UIQI)，u- nidue score index Q4 and average gradient, than wavelet based methods.

Human Abnormal Behavior Recognition Based on Topic Hidden Markov Model

Computer Science. 2012, 39 (3): 251-255.

Abstract

PDF(530KB) ( 577 )

RelatedCitation | Metrics

This paper aimed to address the problem of modeling human behavior patterns captured in surveillance videos for the application of online normal behavior recognition and anomaly detection. From the perspective of cognitive psy- chology,a novel method was developed for automatic behavior modeling and online anomaly detection without the need for manual labeling of the training data set The work has been done with the hierarchical structure,following the rou- tine of "Video Representation-Semantic Behavior (Topic) Model-Behavior Classification":1) A compact and effective behavior representation method is developed based on spatial-temporal interest point detection. 2) The natural grouping of behavior patterns is determined through a novel clustering algorithm, topic hidden Markov model (THMM) built up- on the existing hidden Markov model ( HMM) and latent Dirichlet allocation (LDA) , which overcomes the current limi- tations in accuracy, robustness, and computational efficiency. I}he new model is a four-level hierarchical Bayesian model, in which each video is modeled as a Markov chain of behavior patterns where each behavior pattern is a distribution over some segments of the video. Each of these segments in the video can be modeled as a mixture of actions where each ac- lion is a distribution over spatial-temporal words. 3) An online anomaly measure is introduced to detect abnormal be- havior,whereas normal behavior is recognized by runtime accumulative visual evidence using likelihood ratio test (I_RT) method. Experimental results demonstrate the effectiveness and robustness of our approach using noisy and sparse data sets collected from a real surveillance scenario.

Novel Binary Classification Method for Traditional Chinese Paintings and Caligraphy Images

潘卫国，鲍泓，何宁

Computer Science. 2012, 39 (3): 256-259.

Abstract

PDF(341KB) ( 429 )

RelatedCitation | Metrics

Traditional Chinese painting(TCP) and calligraphy is unique forms of art. With the rapid development of digi tal technology,more and more TC;P and Calligraphy works are digitized. How to effectively retrieve these images be- comes a hot topic. If we first classify the TCP and Calligraphy images, this will be a solid foundation for retrievaling those images. We proposed an improved classification method of those images.‘I_iubai' area was detected firstly, and removed it from the images,because these regions contain noise information which will make the classifation results in- accurate. The second step was to extract feature from those images. At last, the features were used to training the Sup- port Vector Machine(SVM) model. And the trained model was used to classifying the TCP and Calligraphy images. The classification result shows this method has better effect.

Research on Image Blur Algorithm Optimization Using OpenCL

Computer Science. 2012, 39 (3): 260-264.

Abstract

PDF(469KB) ( 594 )

RelatedCitation | Metrics

Modern GPUs generally provide specific hardware(such as texture, grating components and various on-chip cache) to accelerate the 2D image processing and displaying process. Programming model defines specific APIs to facili- fate image applications taking advantage of image-related GPU hardware, such as CUDA' s texture memory and OpenCI_'s Images Object. Taking the optimization of image blur algorithm on AMD GPU as an example, the paper made a deep insight into the using of OpenCL's image object on image applications,especially its advantage and disad- vantage compared to the more general optimization method based on global memory and the on-chip local memory. The experimental results demonstrate that the image object can provide better performance only when the processing image is four-channel and the amount of data to be cached is small. For other cases, optimizing with global memory and local memory can get better performance. After optimization,the speedup reaches 200x to 1000x in comparison with the well optimized CPU code,and the speedup over NV)DIA NPP version is upto 1. 3x to 5x.

Performance Test of Massively Parallel Program on TH-lA

Computer Science. 2012, 39 (3): 265-267.

Abstract

PDF(360KB) ( 390 )

RelatedCitation | Metrics

TH-lA is the china's first petaflops supercomputer and is now installed in national supercomputer center in I}ianjin,which is ranked No. 1 on Top500 list released in Nov. 2010. I}H-lA systcxn adopts a hybrid architecture of hetero- geneous integration of CPU}GPU and self-intellectual high-speed interconnection system,and shows distinguished sys- tem usability, performance stability and application scalability in quite a few high performance computing areas, provides an important platform for science research and technology innovation. In this paper,several largcscale application tests on TH-lA were introduced, such as the oil seismic data processing, aircraft flow field simulation, biomolecular dynamics simulation, magnetic confinement fusion numerical simulation, turbulent flow simulation, crystal silicon molecular dy- namics simulation, fully implicit simulation of global atmospheric shallow wave, heat flow simulation of earth outer core. These results show that TH-lA has good parallel efficiency and scalability in practical applications.

Symbolic Model Checking of Asynchronous FIFO

Computer Science. 2012, 39 (3): 268-270.

Abstract

PDF(241KB) ( 670 )

RelatedCitation | Metrics

Clock domain crossing(CI}C) is an important issue in SoC design and verification. We presented the symbolic model checking of asynchronous FIFO, proposed a finite state machine to model the asynchronous FIFO, then, used SMV to analyze and check its specification described by linear temporal logic. Result shows the design is correct and the method is effective. Compared with simulation and emulation, model checking can save time, run automatically, and does not need test bench.

Parallel Program Design and Implementation on Precipitation Program of Networking Weather Radar System

Computer Science. 2012, 39 (3): 271-275.

Abstract

PDF(418KB) ( 416 )

RelatedCitation | Metrics

Quantitative estimation precipitation system of China Meteorological Administration is comput}intensive and a real-time application. If one work can reduce its execution time, it will bring enormous benefits to the society. First, implementing hotspot analysis and concurrency analysis on serial code with VTune Amplifer XE. Then, parallelizing this program on Intel 4-core platform using both Win32 thread and OpenMP. hhis program has two separated part; single station process and networking process. Because of limited computing resource, the parallel version of single-station process gains only 10 0 o performance increase. But performance of networking process can achieve nearly linear increase. 13y balancing the load of the whole program, parallel version may achieve speedup of 5. 5. And through analysis of meth- ods to parallelize code, summarizing the general method of parallelizing a class of program.

Research on Hardware/Software Task Partitioning for Reconfigurable System

Computer Science. 2012, 39 (3): 276-278.

Abstract

PDF(350KB) ( 535 )

RelatedCitation | Metrics

As the crucial design steps in reconfigurable system development process, the results of the hardware/soft- ware task partitioning directly affect the performance of reconfigurable system. Most of the current hardware/software task partitioning only consider the partitioning results of the application or the algorithm, ignoring the overheads of the FPGA configuration and communication, resulting in the actual result is not satisfactory. I}his paper presented a hard- ware/software task partitioning methods based on performance evaluation,which generates the hardware/software task partitioning results of reconfigurable system by evaluating and testing the overhead of computing, configuration and communication of日'GA, combined with improved simulated annealing algorithm. The experimental results show that the partitioning method has good accuracy and faster convergence speed.

Efficient and Scalable Parallel Algorithm for Motif Finding on Heterogeneous Cluster Systems

Computer Science. 2012, 39 (3): 279-282.

Abstract

PDF(349KB) ( 407 )

RelatedCitation | Metrics

The optimal sequence distribution models for solving Motif finding with length L镇16 and L } 16 were cons tructed respectively and a parallel algorithm to find Motif combining voting algorithm with uniform projection and neighbourhood thresholding algorithm was implemented on the heterogeneous cluster that the processor nodes have dif- ferent computing speed and distinct communication capability. Experimental results show that the parallel Motif finding algorithm using optimal sequence distribution strategy has good speedup and scalability, and it is superior to the parallel algorithm using even distribution strategy.

Lightweight High Performance Computing Environment Monitoring System Based on GMA

Computer Science. 2012, 39 (3): 283-285.

Abstract

PDF(393KB) ( 401 )

RelatedCitation | Metrics

Physics and Computational Mathematics,Beijing 100094,C;hina) Abstract For the general rectuirements of high-performance computing environment monitoring, we analyzed and con trusted the existing monitoring architecture. Based on grid monitoring architecture, we designed and realized a light weight such an and efficient monitoring system, discussed several key issues of the system design in detail. Finally we realized efficient and lightweight monitoring system in high performance computing environment.

Parallel Realization of the MRRR Algorithm Based on CUDA

Computer Science. 2012, 39 (3): 286-289.

Abstract

PDF(343KB) ( 692 )

RelatedCitation | Metrics

The algorithm of multiple relatively robust representations(MRRR) is one of the fastest and most accurate algorithms. After analyzing the MRRR algorithm and CUDA parallel architecture, parallel MRRR algorithm based on CUDA was given, and explored the optimization in memory structure. Compared with LAPACK's MRRR implementa- lion this parallel method provides 20-fold speedups. This result demonstrates the algorithm can be mapped efficiently onto GPU.

Automatic Computation and Data Decomposition Algorithm Based on Dominant Value

Computer Science. 2012, 39 (3): 290-294.

Abstract

PDF(499KB) ( 339 )

RelatedCitation | Metrics

Automatic computation and data decomposition are an optimization technique that distributes computations and data onto different processors. The decomposition result has a direct impact on the performance of program's paral- lelization. Array is one of main targets of treatment for the decomposition algorithm, and some profits of them are not e- nough after parallclization, but it will bring constraints and disrupt the other distribution of array, leading to large a- mounts communication of data re-distribution. The decomposition algorithm in existing has no agreement in the order of array distribution, therefore can't restrict propagation of constraint of array' s parallelization, reducing performance of optimized parallel code automatically generated by the back-end compiler. This paper presented an automatic computa- tion and data decomposition based on the dominant values. Algorithm quantified the impact of array on the programs' parallelism as the dominant value, and agreed priorities of distribution based on the size of the dominant values of array, limited the spread speed of constraints of interference array, improved the reasonableness of decomposition results. Ex- perimental results show that the algorithm can get good decomposition results.

Improved Algorithm for Communication Synchronization on Reconfigurable Mesh with Faults

Computer Science. 2012, 39 (3): 295-298.

Abstract

PDF(458KB) ( 316 )

RelatedCitation | Metrics

Fault tolerant technique for reconfigurable multiprocessor array deals with the issue of reconstruction of the processor array which contains fault units to get the largest available target array. Previous research focused primarily on the reconfiguration algorithm, which does not involve in the study of the synchronous communication performance for reconstructed target array. This paper proposed an optimization algorithm which can improve the performance of the synchronous communication on target array as it reduces the communication delay between neighboring rows for the target array. Experimental results show that the proposed algorithm achieves improvement on communication synchro- nous performance on processor arrays with different scales and different fault densities.

GPU-based Algorithm of Shortest Path

Computer Science. 2012, 39 (3): 299-303.

Abstract

PDF(413KB) ( 1603 )

RelatedCitation | Metrics

As for the all-pairs shortest path problem in the graph, based on parallel algorithm in the CPU cluster envi- ronment, depending on parallel speedup mechanism on the GPU, in order to increase the parallelism and locality, chess- board division method was chosen for task division in this parallel algorithm on the GPU. Because the graph scale is lar- ger than the display memory, the asynchronous parallel algorithm on the GPU was presented. hhe experimental data proves that the algorithm has accelerating effects below compared with CPU with single core: first, for the small graph whose vertexes arc less than 10000, it is about 155 times faster; second,for the large graph whose vertexes arc more than 10000,it is about 25 times faster.

Efficient Method for Histogram Generation on GPU

Computer Science. 2012, 39 (3): 304-307.

Abstract

PDF(374KB) ( 709 )

RelatedCitation | Metrics

Histogram generation is an inherently sequential loop computation with irregular data dcpcndcncc,which has a full range of applications in diverse fields. However, the presence of irregular memory access in histogram loop nest poses an obstacle to its paralleled execution using a massive number of fincgrained threads due to access latency leaded by bank conflicts. It is non-trivial to accelerate histogram generation algorithm on parallel platform, particularly on the state-of-the-art parallel platform, graphics processing unit (GPU). For reducing bank conflicts, utilization of padding technique can evenly distribute shared memory access of multiple threads to different banks and largely exploit GPU's potential on accelerating histogram generation. Moreover, efficient near-optimal configuration search model can guide programmers choosing appropriate GPU execution parameters for higher performance. Experimental result demon- strates the improved histogram generation algorithm has approximate 42 0 o to 88 0 o speedups than traditional histogram generation algorithm on GPU.

Research on Pre-processing Methods of Unstructured Grids

Computer Science. 2012, 39 (3): 308-311.

Abstract

PDF(391KB) ( 781 )

RelatedCitation | Metrics

The preprocessing methods of unstructured grids arc one of the important technologies for unstructured grids CFI)parallel computing. The paper supplied a new efficient and robust fast search algorithm to build the relation- ship graph of the global unstructured cells,which is based on buffer data structure and can be easily implemented with low complexity. And the paper brought forward the reordering algorithm to deal with the out of-order problem brought by unstructured grids,which can improve the computing efficiency and can be used in all kinds of unstructured grids. Experiment results show that even in the case of complicated areas of large grids number, the pre-processing methods can get good performance.

Research of LDPC Encoding and Decoding Simulating Realization under WiMAX

Computer Science. 2012, 39 (3): 312-315.

Abstract

PDF(311KB) ( 486 )

RelatedCitation | Metrics

Encoding under WiMAX is a hot topic in today's telecommunication technology research. hhis paper intro- duced one of the most popular error correction encoding; Low Density Parity Check code (LDPC code)，discussed the basic principle and encoding-decoding design of LDPC code under WiMAX，put forward a LDPC code simulating plat- form by using Visual C++ characters, studied the procedure of simulation design, analyzed the impact to LDPC code performance under different realization method, and by analyzing and studying of simulation results, explained the feasi- bility, practicability and expansibility of Visual C++ applied in LPIX; encoding-decoding simulation.