ISSN 1000-1239 CN 11-1777/TP

Table of Content

15 June 2010, Volume 47 Issue 6
Parallel Load-Balancing Performance Analysis Based on Maximal Ratio of Load Offset
Zhang Lilun, Ye Hong, Wu Jianping, and Song Junqiang
2010, 47(6):  . 
Asbtract ( 568 )   PDF (744KB) ( 470 )  
Related Articles | Metrics
It is well known that the measurement of load-balancing and its effect on the whole performance of massively parallel applications is a tough job. In this work, an evaluation model of load-balancing is put forward for numerical parallel computing based on local discretization schemes (finite difference, finite element, etc.). By introducing the maximal ratio of load offset (MRLO) as the index of load-balance, the quantitative relationships between the parallel efficiency and the ratio of computing to communication, parallel scale, problem size, and complexity of numerical schemes are analysed. MRLO is a basal parameter of the evaluation model. A famous global ocean circulation model named POP benchmark is used for verification of the evaluation model. Since the ratio of walltime cutdown is equal to that of efficiency improvement, the parallel efficiency increase of POP can be predicted from both walltime and the evaluation model. The evaluation model reveals that to what extent the whole performance depends upon load-balancing. Especially for large-scale parallel computing, load-balancing is more and more sensitive to parallel efficiency with the increase of problem size and parallel scale. The result shows that load-balancing is an important bottleneck of parallel computing up to tens of thousands tasks, and researchers of parallel optimization for all kinds of applications should put more emphases on load-balancing.
Guarder: Virtual Drilling System for Crowd Evacuation Under Emergency Scheme
Wang Zhaoqi, Mao Tianlu, Jiang Hao, and Xia Shihong
2010, 47(6):  969-978. 
Asbtract ( 930 )   HTML ( 12)   PDF (3210KB) ( 829 )  
Related Articles | Metrics
Large-scale public places and essential public facilities are areas with highly concentrated population. In order to safely evacuate peoples in emergency situations, it is necessary to make emergency schemes for such areas in advance. However, making emergency scheme for such places and facilities is very difficult due to their high complexity in architecture and high density population. Virtual drilling of crowd evacuation under emergency scheme is a new technology to hit these problems. By using virtual reality technique, 3D virtual crowds and public facilities are generated in computer generated space and the process of evacuation is simulated under the given assumption of security crises and emergency scheme. The authors could also 3D-display the scenes of evacuation and statistically analyze the results, which are very useful for verifying the rationality and validity of the given emergency scheme. This paper introduces a system named Guarder, which is a virtual drilling system for crowd evacuation under emergency scheme. The core idea and technical framework of the system are introduced in details. Key technologies including semantic description for complex environment, crowd simulation and so on are deeply introduced. After that, several experiments and applications of the system Guarder are demonstrated to show the success of the technique design in Guarder. Moreover, some hot research topics are presented.
Research on Motion Simulation Realization Technology of Planar Linkage Based on Virtual Environment
Zhang Zhixian, Liu Jianhua, and Ning Ruxin
2010, 47(6):  979-987. 
Asbtract ( 390 )   HTML ( 0)   PDF (2020KB) ( 565 )  
Related Articles | Metrics
Mechanism motion simulation based on virtual assembly is a very important step to products assembly motion in virtual environment. Mechanism motion simulation after finishing assembly simulation in virtual environment can provide effective reference data for analyzing the mechanism performance so as to analyze whether the mechanism is logical and improve the quality of assembly. First of all, combined with the development of mechanism motion simulation both home and abroad, the essential idea and the whole frame of realizing the mechanism motion simulation based on virtual assembly technology are presented in virtual environment, and the geometrical method which is utilized to solve the problem and calculate the kinematic parameters of mechanism motion simulation is proposed by taking an example. Geometrical method divides one mechanism into some basal groups so as to analyze the kinematics regularity of these basal groups instead of analyzing the kinematics regularity of the whole mechanism. Secondly, the key algorithms of automatic recognition of kinematic pair, automatic search of mechanism and mechanism identification are discussed. These algorithms have important significance for reducing the workload of pretreatment of mechanism motion simulation after finishing assembly simulation in virtual environment so as to promote the level of automatization of simulation effectively. Finally, all the methods are implemented and validated in the prototype system the Virtual Assembly Process Planning (VAPP).
A Real-Time Rendering Method for Large Terrain Including Details in Different Resolutions
Yu Zhuo, Liang Xiaohui, Ma Shang, and Zhao Qinping
2010, 47(6):  988-995. 
Asbtract ( 338 )   HTML ( 1)   PDF (1647KB) ( 610 )  
Related Articles | Metrics
In order to improve the capacity of performance of large scale terrain data, users usually create detail data by editing way such as changing the features in some regions and add other details to original terrain data in some simulation training or video games. However, its a big challenge to merge and render large terrain and additional detail data in real time due to different resolutions. In this paper, a new algorithm is given to handle this problem. In preprocessing stage, the algorithm constructs large terrain by clipmap structure as to integrating advantages of geometry clipmap method and constructs the detail data in mipmap way. In real-time rendering phase, the phenomenon of “F” hole area appears at the boundary between the large terrain and the detail data when clipmap structure is being updated. In order to solve this problem, a new structure called transition strip is proposed which can merge the data in different resolutions well in run time, the transition strip structure is given which is composed of two sides, the vertexes in lower resolution and vertexes in higher resolution. Some transition strips are used to fill the “F” hole area and these transition strips are close to each other in practice. And a fast triangulation method used for rendering. The results of experiments show that the transition strip can solve the problem of “F” hole area and can render both large terrain and details data in real time.
Multiresolution Data Organization and Interactive Visualization in JaVis
Xu Pingjun, Shen Weichao, and Liao Li
2010, 47(6):  996-1004. 
Asbtract ( 679 )   HTML ( 3)   PDF (1604KB) ( 516 )  
Related Articles | Metrics
With the rapid development of high performance computer and technology, scientists can model complex physical phenomena at a scale and fidelity to answer some of the most important and difficult questions in science. The output from these simulations, however, is so voluminous and complex that advanced visualization technologies are necessary to interpret the calculated results. Even though visualization technology has progressed significantly in recent years, it is difficult to visualize and analyze terascale or much larger data interactively to full extent. Interactive speed of dealing with large data embarrasses the operation of data visualization and analysis severely. How to reduce I/O data size and improve interactive speed are the main challenges in developing visualization system designed for large scale data analysis. Many studies indicate that multiresolution technique is an important and feasible means of addressing these problems. In this paper the authors present some new multiresolution techniques implemented in JaVis, a large-scale data analysis and visualization system, to accelerate interactive visualization of large dataset. The key techniques developed are summarized as follows: multiresolution data organization, multiresolution data operator plugin implementation and multi-level data switch. Also demonstrated are the efficiency and robustness of the interactive visualization techniques with some real physical datasets.
A Servocontrol-Based Augmented Reality Registration Method for Digital Reconstruction of Yuanmingyuan Garden
Huang Yetao, Liu Yue, Weng Dongdong, and Wang Yongtian
2010, 47(6):  1005-1012. 
Asbtract ( 426 )   HTML ( 0)   PDF (1783KB) ( 742 )  
Related Articles | Metrics
Registration in three dimensions is one of the most important and difficult issues in outdoor augmented reality system. A servocontrol-based registration method is designed for robust registration. The proposed method can improve the accuracy of the registration without the requirement for improving tracker itself. Taking the outdoor environment and requests of historical site reconstruction into account, inertial tracking is adopted for head tracking. With the orientation data obtained by inertial tracker, the real camera is controlled as a follow-up rotation. The real camera is fixed on a high speed rotational table which is driven by a stepping motor with a high precision. At the same time, the virtual camera in three-dimension virtual world is also controlled by the same orientation data. Thus, different from the conventional registration method, the servo-control system manages to avoid the influence of errors from tracker on the combination of virtual and real world. The building of camera model in virtual world, calibration of real camera and registration in rendering engine are also discussed. The error and time lag is tested by experiments. Experimental results show the improvements of the proposed method on stability and accuracy. The application of the proposed system in the digital reconstruction of Yuangmingyuan Garden indicates its potential to be used in real scene.
3D Fingertip Tracking Algorithm Based on Computer Vision
Guo Kangde, Zhang Mingmin, Sun Chao, Li Yang, and Tang Xing,
2010, 47(6):  1013-1019. 
Asbtract ( 549 )   HTML ( 0)   PDF (1051KB) ( 505 )  
Related Articles | Metrics
Realtime human-computer interaction(HCI) based on hand gestures plays an important role in both theory and application of virtual reality. Since the 3D position of fingertip can be tracked and located through stereovision technology with two cameras, the real-time interaction between fingertip and 3D objects in virtual world can be achieved. The proposed method in this paper can be widely used to implement 3D interaction for augmented reality based video games. In this paper, an improved BGS algorithm, which combines threshold decision with GMM, is presented to identify the hand region. The method can get hand region in different lighting conditions, and avoid the interference of cast shadow of hand. The fingertip can be determined with contour Kvector and distance between the hand region center and the candidate fingertip position. Compared with the general fingertip algorithms, the algorithm presented can get fingertips in unfriendly hand foreground segmentation. After calibrating two cameras, the authors get origin position in world coordinate relative to marker center, then 3D position of fingertip can be reconstructed by camera parameters and the fingertip positions in two images taken by the two cameras. Finally, Kalman filter is employed in 3D space to smooth the fingertip trajectory and predict the range of fingertips. Experimental result shows the efficiency of the algorithm.
The Scene Simulation of Crowd Behaviors Oriented to Strategic Decision-Making
Yu Haiquan, Si Guangya, Yang Zhimou, and Luo Pi
2010, 47(6):  1020-1025. 
Asbtract ( 453 )   HTML ( 0)   PDF (1697KB) ( 515 )  
Related Articles | Metrics
The scene simulation of crowd behavior for strategic decision-making need to process large-scale data calculation and graph rendering. So, it is difficult to perform this simulation with a personal computer. In this paper, firstly, the collectivity technical project of this kind simulation is constructed. Secondly, the design of how to create the three-dimension virtual persons model is discussed. Then, how to catch the persons behaviors and the bodys actions is described detailedly and the database of persons behaviors and the bodys actions is created. Subsequently, the methods of how to describe the whole scene effect of crowd behavior simulation with the platform of Geofusion and how to render the living scene effect of crowd behavior simulation with OpenGVS are fully and accurately proposed. Finally, applying the proposed crowd behavior simulation method, the scene simulation of crowd behaviors acquires favorable effect. This makes the strategic decision-maker more clearly understand the war actions influence on crowd of community and know the degree of influence which the war brings on. It can supply the technique and information for strategic decision-maker. So this paper has important significance for improving the rationality and veracity of strategic decision-making.
A Parallel Algorithm for Multi-Resolution Representation of DEM Based on Discrete Wavelet Analysis
Huang Wei, Wei Yingmei, Song Hanchen, and Wu Lingda
2010, 47(6):  1026-1031. 
Asbtract ( 451 )   HTML ( 2)   PDF (1095KB) ( 517 )  
Related Articles | Metrics
Because of the discrete wavelets characteristics of multi-resolution, discrete wavelet transformation can be used to construct multi-resolution of the DEM data. Nevertheless, the intensive computation of DWT has become a significant bottleneck in real-time applications when the size of DEM data is large enough. It presents a parallel processing framework to overcome the drawbacks of this problem and achieves a fast parallel building of the DEM datas multi-resolution model. As the DEM data is equivalent to two-dimensional gray-scale images, it can be processed as two-dimensional signal. This paper first gives the Mallat algorithm for a two-dimensional discrete wavelet transform (DWT). Based on this algorithm, the parallel property of the DWT is analyzed. Result shows that the Mallat algorithm is easy to carry out in parallel mode because of the local nature of the DWT. Then analyzed are the data communications between the logical topology of the multi-processors. Concretely, the authors present a data structure of the local array declared on the processor and describe the communication relationships between the various processors on two-dimensional grids. Simulation tests show that the parallel model leads to a satisfactory scalability of the algorithm and high speedups are achieved.
Real-Time Rigid Body Fracturing Simulation
Zeng Liang, Wu Yagang, and Li Sikun
2010, 47(6):  1032-1037. 
Asbtract ( 490 )   HTML ( 0)   PDF (1536KB) ( 517 )  
Related Articles | Metrics
Rigid body dynamics has been of great interest to the computer graphics researchers for a long time, especially during the latest decade. Purely physical based simulation is not a good solution for the virtual reality application environment because of its low real-time feature; researchers have to balance the simulation speed and the visual effect. Based on the attackers track, an effect algorithm for locking to-be destroyed area is designed. Octree is used to structure the targets geometry model, and then spatial continual subsets in the local area are extracted according to the attacker collision position. A pre-fracturing pattern for rigid body simulation is proposed in this paper. Linear constraints are used to connect the subsets and their fundamental elements. At the same time the whole local area and the other part of the target are connected by the linear constraints too. A unified algorithm will detect how the constraints are impacted, which will lead to fracture effect. Once the constraint is broken, the subsets or the elements will be separated. Different attackers will lead to different levels of fracture. The key reason is that the linear constraint impacted is dynamic due to the attackers collision degree. Finally, a real time rigid body fracturing effect simulation system is designed. Experiments show that the pattern works well and predigests some complexity, and it could be applied in the virtual reality environment requiring real-time feature.
Earthquake Disaster Scenario Simulation Technology
Jia Qunlin and Zhou Baijia
2010, 47(6):  1038-1043. 
Asbtract ( 700 )   HTML ( 9)   PDF (1902KB) ( 648 )  
Related Articles | Metrics
Earthquake is a huge devastating and paroxysmal natural disaster. Emergency leaders have to do several jobs during the response to earthquake. In order to do the right job they must be trained. Training can be done by using several techniques and methods. One of the methods is virtual training. Doing training with virtual training simulation give the opportunity to train leaders without numbers of persons that are normally needed for training. Virtual emergency rescue training simulation is one of virtual simulation research areas. The realistic extent of earthquake virtual scene is to determine the effect of virtual simulation training. The purpose of this paper is to build virtual disaster scenario. Because the earthquake disaster is very complicated, its not possible to simulate every aspect of earthquake disaster scenario in detail. In this paper, by studying the formation of building collapse and the collapse of buildings in the distribution of space, sub-model way to build the scene, secondary disaster simulation methods, scenes integration approach, the authors discuss how to build a relatively realistic virtual earthquake disaster scenario. The research of this paper has laid a foundation for the research and development of virtual simulation training systems, and provided a theoretical basis for the visual simulation modules.
A Density-Based Clustering Algorithm Concerning Neighborhood Balance
Wu Jiawei, Li Xiongfei, Sun Tao, and Li Wei
2010, 47(6):  1044-1052. 
Asbtract ( 493 )   HTML ( 5)   PDF (816KB) ( 707 )  
Related Articles | Metrics
Clustering is an important analytical tool in data mining. Density-based clustering analysis is a clustering analysis method which is demanded to deal with very large databases. By analyzing the limitation of the existing density-based clustering algorithms and the problems of disposing various densities of data and illegibility of clusters boundaries, definitions such as projection points, neighborhood balance, balanceable core points, and boundary sparse points are introduced. After analyzing the distribution characters of core points and points in their neighborhood, a density based clustering algorithm bDBSCAN concerning the neighborhood balance of core points is proposed to improve DBSCAN. The algorithm deals with the core points by getting the projection of the points in their neighborhood to judge whether they are balanceable. Only balanceable core points can be expanded to form clusters. The algorithm can discover clusters with arbitrary shape and various data distribution characters effectively and efficiently and eliminate noise such as boundary sparse points. The theoretical analysis and experimental results indicate that the algorithm improves the accuracy of clustering and offers better results of clustering on various data sets and solves the difficulties of clustering high dimensional spatial data such as indistinct boundary between clusters, too many noise data points, etc. Meanwhile the choice and impact of the parameter in the algorithm are discussed.
Computing the Least Common Subsumer in Description Logic FLEN
Zhang Wei, Hou Jinhong, Cao Fasheng, Wang Ju, and Jiang Yuncheng5,6
2010, 47(6):  1053-1059. 
Asbtract ( 477 )   HTML ( 3)   PDF (628KB) ( 478 )  
Related Articles | Metrics
Description logics are formalisms that can represent knowlwdge. Every description logic system contains two parts: One is knowledge base and the other is reference service. Typically, these services include subsumption and instance checking, both of which are called standard inference in description logic. But standard inferences provide little help in constructing and maintaining large DL knowledge bases, so researchers proposed another kind of inferences called nonstandard inference. Nonstandard inference in description logic is a main issue that researchers are focusing on, it mainly includes the most specific concept, the least common subsumer, matching, rewriting and so on. Previous works mainly concerntrates on kinds of description logic systems which dont contain number restriction. Analyzed in this paper is the least common subsumer in description logic FLEN, which contains the number restriction and existential restriction at the same time. It will provide some probabilities to solve the matching problem in description logic with existential restriction and number restriction. Firstly the FLEN-concept description tree and the homomorphisms on description trees are defined and then the subsumption relationship between concepts is characterized by computing the homomorphisms between their description trees. After that the product of two description trees is defined and an algorithm to compute the least common subsumer is proposed by the product of the description trees, and it is pointed out that the size of least common subsumer of two concept descriptions A,B is exponential of the size of A and B.
NU2RA: An Analysis Method for Range Queries over Uncertain Moving Objects in Road Networks
Chen Yifei, and Qin Xiaolin
2010, 47(6):  1060-1069. 
Asbtract ( 522 )   HTML ( 0)   PDF (1728KB) ( 530 )  
Related Articles | Metrics
The positions of moving objects are assumed to be exactly known in most researches on different types of queries. In fact, except for updating instants, moving objects exact locations are not known, but are bounded by uncertainty regions. So the algorithms based on precise positions are inapplicable. Existing algorithms that involve uncertainty concern either uncertain querying objects or uncertain interesting objects moving in Euclidean space. Aiming at the uncertain range queries over uncertain objects constrained in road network, an analysis method named NU/+2RA is proposed here. The length of shortest path instead of the Euclidean distance is used. Network distances between two uncertain objects are defined. The network is partitioned into 5 parts according to uncertain query ranges. Possible distributions of objects are represented with distribution codes, and 22 kinds of topological relations between uncertain objects and uncertain ranges are identified. Query answers are augmented with probabilistic guarantees of the validity of answers. Probability evaluation in each case is derived. NU/+2RA, being independent of concrete uncertain moving objects models, provides the general topology analysis and probability evaluation for uncertain range queries in road network. The method is applicable to both uncertain history trajectories and uncertain current and near future motions of moving objects.
Effective XML Vague Content and Structure Retrieval and Scoring
Liu Xiping, Wan Changxuan, and Liu Dexi
2010, 47(6):  1070-1078. 
Asbtract ( 330 )   HTML ( 2)   PDF (1234KB) ( 445 )  
Related Articles | Metrics
XML documents involve both contents and structures, and can be retrieved by means of not only content-only (CO) but also content-and-structure (CAS) queries. In this paper, a novel approach for CAS retrieval is proposed. The approach proceeds in three steps: it first decomposes a CAS query into a set of query fragments, and then processes each query fragment. Finally, it combines results on each query fragments. By this approach, on the one hand, the adverse effects of structural vagueness on answer nodes selection can be removed; on the other hand, the effect of structural constraints on scoring is incorporated properly. The features of this approach make it applicable in versatile homogeneous and heterogeneous data environments. To measure the relevance query results to a given CAS query, a novel scoring scheme is presented. In accordance with the query processing approach, the scoring method first computes the scores of a query result with respect to each query fragment, and then combines these partial scores to arrive at an overall score. The proposed scoring method considers the relevance of both contents and structures in the retrieval results, and thus reflects the users query intention and conforms to query semantics. Comprehensive experimental studies demonstrate the effectiveness of the proposed methods.
Nested Loop Join Optimization Based on Radix-Join in Chip Multi-Processor
Deng Yadan, Jing Ning, and Xiong Wei
2010, 47(6):  1079-1087. 
Asbtract ( 685 )   HTML ( 0)   PDF (1490KB) ( 840 )  
Related Articles | Metrics
Aiming at current chip multi-processor(CMP), presented in this paper is a non-indexed nested loop join (NINLJ) optimization based on shared cache CMP. The authors firstly present multithreaded NINLJ execution framework based on radix-NL-join algorithm, and then, through reducing cache conflict and improving cache hit ratio, optimize cache performance of cluster partition thread and cluster join thread in the framework. The main contributions are as follows: 1.Aiming at the shared cache confliction when multiple threads access shared cache simultaneously, the start time of cluster partition thread is optimized to reduce shared cache confliction in cluster partition phase; 2. In cluster join phase, cluster join threads have poor cache behaviors. To solve this performance bottleneck, the advantage of sequent cluster access is utilized when cluster join threads executing, and preload thread is adopted to preload cluster from main memory to L2-cache before cluster join threads need it; 3.In the experiments, the framework is realized in EaseDB, and the performance of multithreaded NINLJ is tested. The experiment results show that the multithreaded NINLJ execution framework could fully utilize computing resource of CMP and effectively solve shared cache conflict in multithreaded environment, and the performance of NINLJ is improved. The algorithm proposed outperforms traditional multithreaded Radix-NL-Join by 26% on average.
A Publish/Subscribe Based Information Dissemination Model for QoS of Web Services
Zheng Xiao, Luo Junzhou, Cao Jiuxin, and Song Aibo
2010, 47(6):  1088-1097. 
Asbtract ( 705 )   HTML ( 1)   PDF (2234KB) ( 498 )  
Related Articles | Metrics
Quality of service (QoS) information for Web services is essential to QoS-aware service management. Currently, most work assumes that the overall QoS of a composite service can be computed by the pre-existing QoS information of component services. However, the issue of how to obtain these QoS information has largely been overlooked. Current research on this problem usually involves query-based or monitoring-based methods. However, in a dynamic service oriented computing (SOC) environment, these solutions suffer from some or all of the limitations, such as cost, timeliness guarantee and scalability. In this paper, a P2P based publish/subscribe model is proposed to disseminate new revised QoS information of Web services, which not only maintains the scalability of the underlying Chord network, but also improves reliability and timelines guarantee especially for QoS information obtainment. The authors suggest specialized rendezvous points(RPs) and a replica mechanism to reduce the risk of subscriptions loss and consequently improve reliability. A reverse RP ring is designed to quicken subscription delivery and QoS information publication. In addition, an optimization mechanism for composite services is built into the proposed model, which helps to reduce notification traffic. Simulation results show that the model is featured by low cost, high efficiency and scalability, which is suitable to large-volume QoS information distribution.
A Consecutive-Behaviors-Observing-Based Neighbor Evaluation Model in P2P Network
Xie Zhen, Bi Jingping, and Li Ye,
2010, 47(6):  1098-1106. 
Asbtract ( 464 )   HTML ( 0)   PDF (1828KB) ( 513 )  
Related Articles | Metrics
Reputation based trust mechanism has been identified as an effective method to evaluate peers behavior and which is employed to secure the applications in P2P network. Trust mechanism is such a mechanism that relies on other peers reports, which are also called local trust, to evaluate a designated peer. However, the existence of strategic peers and human judgment error is a big challenge, which makes the local trust hard to reflect peers type. Furthermore, it increases the estimation error of global trust. The authors propose a new model, called PeerStrategy, to evaluate neighbors behavior in P2P network. This model explores deterministic finite automaton (DFA) to describe the variance of neighbors consecutive behaviors. The DFA consists of seven states and it transits between states by neighbors performance in the interactions. By examining the probability of negative behaviors in any consecutive ones, the model can not only detect strategic peers accurately but also tolerate human judgment error. As a result, this model improves the accuracy of local trust, and whats more, it decreases the estimation error of global trust. The simulation shows that this model improves the accuracy of local trust considerately and also diminishes the influence on the estimation error of global trust, and it performs the best compared with other current methods.
An Integrity Checking Scheme in Outsourced Database Model
Xian Hequn, and Feng Dengguo
2010, 47(6):  1107-1115. 
Asbtract ( 528 )   HTML ( 0)   PDF (965KB) ( 761 )  
Related Articles | Metrics
In the outsourced database model, databases face potential threats from malicious database service providers. Security mechanisms are needed to assure the queriers that the query results have not been tempered with and are authentic with respect to the actual data owner. As an improvement of the existing authenticated-data-structure-based methods, a new integrity checking scheme is proposed using the masked authenticating B/++-tree (MABTree) as the underlying data structure. Common computational information is extracted from the MABTree and is stored in two mask vectors, so as to make the computation in the data structure more efficient. By avoiding mass exponential computation, the scheme reduces both the computational overhead in the integrity check process and the verification time of the query results. The MABTree is designed to support incremental updating, which makes the scheme more efficient when the owner updates the data and the authenticated data structures are updated accordingly. The security proof of the scheme is presented together with the formal definition of the MABTree. Experiments show that, compared with the existing methods, the proposed scheme has a better performance in query verification and a much better performance in the authenticated data structure updating operations.
Research on a Real-Time Task Scheduling Algorithm for Hybrid Reconfigurable System-on-Chip
Liu Yan, Li Renfa, Xu Xinda, and Xu Cheng
2010, 47(6):  1116-1124. 
Asbtract ( 532 )   HTML ( 0)   PDF (1200KB) ( 538 )  
Related Articles | Metrics
Todays reconfigurable hardware devices have huge densities and partially dynamically reconfigurable, allowing for the configuration and execution of hardware tasks in a real multitasking manner. This makes reconfigurable platforms an ideal target for many special application areas, such as embedded system that combines high computation demands with dynamic task sets. The key issues of software running on this platform are online task scheduling and hardware resource management. Finding the available start time and empty space for arrival tasks on FPGAs with runtime partially reconfigurable abilities is the most important phase in on-line scheduling algorithm. The scheduling of hardware task has the highest impact on the performance of the reconfigurable computing system. Presented in this paper is a group-contiguous algorithm which evaluates placement position based on task group information, and the notion of task contiguous for scheduling algorithm is introduced. By utilizing the temporal information and optimized place strategy, the proposed algorithm achieves high scheduling performance and reduces the waste of reconfigurable resources. Simulation experiments conducted with synthetic workloads evaluate the performance and the runtime efficiency of the proposed schedulers. The simulation results show that using the GC algorithm, higher task accept ratio can be achieved than using other existent scheduling algorithms.
Advances in Image Coding Based on Multiscale Geometric Analysis
Wang Xianghai, Sun Qiang, Song Chuanming, and Liu Dan
2010, 47(6):  1132-1143. 
Asbtract ( 559 )   HTML ( 1)   PDF (1763KB) ( 681 )  
Related Articles | Metrics
Recently built upon the theory of wavelet analysis, a series of mathematical transforms have been explored that can effectively represent and process high-dimensional singularities. These novel transforms are generally referred to as “multiscale geometric analysis (MGA)”. The objective of MGA is to establish an optimal transform that provides multiscale and multidirectional representation for high-dimensional functions. They have many good characteristics such as multiresolution, time-frequency localization, multi-directionality, as well as anisotropy. Meanwhile, MGA overcomes the limitations of wavelet in representing higher-dimensional singularities, such as edges and contours. So far, the theory and application of MGA have attracted extensive attention from different disciplines of image processing. Among these disciplines, MGA shows great potential for image coding since it can provide a sparser representation than wavelet. Research on MGA-based approach thus has become a focus in the field of image coding in recent years. In this paper, the authors first discuss the directionality of wavelet transform and its limitations. Then taking the development of MGA as thread, they summarize state-of-the-art image coding methods based on MGA. By comparative study, the advantages and drawbacks of each kind of methods are analyzed and discussed. Finally, they state the possible new directions of MGA-based image coding in further developments.