Bimonthly    Since 1986
ISSN 1000-9000(Print)
CN 11-2296/TP
Indexed in:
Publication Details
Edited by: Editorial Board of Journal Of Computer Science and Technology
P.O. Box 2704, Beijing 100190, P.R. China
Sponsored by: Institute of Computing Technology, CAS & China Computer Federation
Undertaken by: Institute of Computing Technology, CAS
Distributed by:
China: All Local Post Offices
Other Countries: Springer
  • Table of Content
      15 November 2006, Volume 21 Issue 6 Previous Issue    Next Issue
    For Selected: View Abstracts Toggle Thumbnails
    Hybrid Nanoelectronics: Future of Computer Technology
    Wei Wang, Ming Liu, and Andrew Hsu
    Journal of Computer Science and Technology, 2006, 21 (6): 871-886 . 
    Abstract   PDF(924KB) ( 1930 )   Chinese Summary
    Nanotechnology may well prove to be the 21st century's new wave of scientific knowledge that transforms people's lives. Nanotechnology research activities are booming around the globe. This article reviews the recent progresses made on nanoelectronic research in US and China, and introduces several novel hybrid solutions specifically useful for future computer technology. These exciting new directions will lead to many future inventions, and have a huge impact to research communities and industries.
    References | Related Articles | Metrics
    Low-Complexity Bit-Parallel Multiplier over GF(2$^m$) Using Dual Basis Representation
    Chiou-Yng Lee, Jenn-Shyong Horng, and I-Chang Jou
    Journal of Computer Science and Technology, 2006, 21 (6): 887-892 . 
    Abstract   PDF(319KB) ( 1333 )   Chinese Summary
    Recently, cryptographic applications based on finite fields have attracted much attention. The most demanding finite field arithmetic operation is multiplication. This investigation proposes a new multiplication algorithm over GF(2^m) using the dual basis representation. Based on the proposed algorithm, a parallel-in parallel-out systolic multiplier is presented. The architecture is optimized in order to minimize the silicon covered area (transistor count). The experimental results reveal that the proposed bit-parallel multiplier saves about 65% space complexity and 33% time complexity as compared to the traditional multipliers for a general polynomial and dual basis of GF(2^m).
    References | Related Articles | Metrics
    Toward the Optimal Configuration of Dynamic Voltage Scaling Points in Real-Time Applications
    Hui-Zhan Yi and Xue-Jun Yang
    Journal of Computer Science and Technology, 2006, 21 (6): 893-900 . 
    Abstract   PDF(344KB) ( 1218 )   Chinese Summary
    In real-time applications, compiler-directed dynamic voltage scaling (DVS) could reduce energy consumption efficiently, where compiler put voltage scaling points in the proper places, and the supply voltage and clock frequency were adjusted to the relationship between the reduced time and the reduced workload. This paper presents the optimal configuration of dynamic voltage scaling points without voltage scaling overhead, which minimizes energy consumption. The conclusion is proved theoretically. Finally, it is confirmed by simulations with equally-spaced voltage scaling configuration.
    References | Related Articles | Metrics
    Parallel Error Detection for Leading Zero Anticipation
    Ge Zhang, Wei-Wu Hu, and Zi-Chu Qi
    Journal of Computer Science and Technology, 2006, 21 (6): 901-906 . 
    Abstract   PDF(318KB) ( 1486 )   Chinese Summary
    The algorithm and its implementation of the leading zero anticipation (LZA) are very vital for the performance of a high-speed floating-point adder in today's state of art microprocessor design. Unfortunately, in predicting "shift amount" by a conventional LZA design, the result could be off by one position. This paper presents a novel parallel error detection algorithm for a general-case LZA. The proposed approach enables parallel execution of conventional LZA and its error detection, so that the error-indication signal can be generated earlier in the stage of normalization, thus reducing the critical path and improving overall performance. The circuit implementation of this algorithm also shows its advantages of area and power compared with other previous work.
    References | Related Articles | Metrics
    Test Time Minimization for Hybrid BIST of Core-Based Systems
    Gert Jervan, Petru Eles, Zebo Peng, Raimund Ubar, and Maksim Jenihhin
    Journal of Computer Science and Technology, 2006, 21 (6): 907-912 . 
    Abstract   PDF(411KB) ( 1211 )   Chinese Summary
    This paper presents a solution to the test time minimization problem for core-based systems. We assume a hybrid BIST approach, where a test set is assembled, for each core, from pseudorandom test patterns that are generated online, and deterministic test patterns that are generated off-line and stored in the system. In this paper we propose an iterative algorithm to find the optimal combination of pseudorandom and deterministic test sets of the whole system, consisting of multiple cores, under given memory constraints, so that the total test time is minimized. Our approach employs a fast estimation methodology in order to avoid exhaustive search and to speed-up the calculation process. Experimental results have shown the efficiency of the algorithm to find near optimal solutions.
    References | Related Articles | Metrics
    Priority-Based Routing Resource Assignment Considering Crosstalk
    Yi-Ci Cai, Bin Liu, Yan Xiong, Qiang Zhou and Xian-Long Hong
    Journal of Computer Science and Technology, 2006, 21 (6): 913-921 . 
    Abstract   PDF(417KB) ( 1248 )   Chinese Summary
    Crosstalk has become one of the most critical concerns in very deep sub-micron era. This paper deals with the problem of crosstalk mitigation at both methodological and algorithmic levels. Noting that intermediate operations between global routing and detailed routing are very effective in crosstalk estimation and reduction, the authors propose to incorporate several intermediate steps that are separated in traditional design flow into an integrated routing resource assignment stage, so that the operations could easily cooperate to fully exert their power on crosstalk reduction. An efficient priority-based heuristic algorithm is developed, which works slice by slice. Crosstalk avoidance, and many other aspects that are critical in routing practice including congestion, vias, layer preference, etc., are taken into account. A track reservation strategy is adopted in the algorithm framework to compensate the undesired effects caused by sequential routing. Experimental results on a series of ISPD98 and industrial benchmarks show that the proposed approach is able to reduce capacitive crosstalk by about 70\% on average without compromising completion ratio compared with a previously reported graph based algorithm, demonstrating the advantages of the approach.
    References | Related Articles | Metrics
    General Floorplans with L/T-Shaped Blocks Using Corner Block List
    Yu-Chun Ma, Xian-Long Hong, She-Qin Dong, C. K. Cheng, and Jun Gu
    Journal of Computer Science and Technology, 2006, 21 (6): 922-926 . 
    Abstract   PDF(488KB) ( 1324 )   Chinese Summary
    With the recent advent of deep submicron technology and new packing schemes, the components in the integrated circuit are often not rectangular. On the basis of the representation of Corner Block List (CBL), we propose a new method of handling rectilinear blocks. In this paper, the handling of the rectilinear blocks is simplified by transforming the L/T-shaped block problem into the align-abutment constraint problem. We devise the block rejoining process and block alignment operation for forming the L/T-shaped blocks into their original configurations. The shape flexibility of the soft blocks, and the rotation and reflection of L/T-shaped blocks are exploited to obtain a tight packing. The empty rooms are introduced to the process of block rejoining. The efficiency and effectiveness of the proposed method are demonstrated by the experimental results on a set of some benchmark examples.
    References | Related Articles | Metrics
    Influences of Gate Operation Errors in the Quantum Counting Algorithm
    Qing Ai, Yan-Song Li, and Gui-Lu Long
    Journal of Computer Science and Technology, 2006, 21 (6): 927-931 . 
    Abstract   PDF(292KB) ( 1372 )   Chinese Summary
    In this article, the error analysis in the quantum counting algorithm is investigated. It has been found that the random error plays as important a role as the systematic error does in the phase inversion operations. Both systematic and random errors are important in the Hadamard transformation. This is quite different from the Grover algorithm and the Shor algorithm.
    References | Related Articles | Metrics
    Verification of Authentication Protocols for Epistemic Goals via SAT Compilation
    Kai-Le Su, Qing-Liang Chen, Abdul Sattar, Wei-Ya Yue, Guan-Feng Lv, and Xi-Zhong Zheng
    Journal of Computer Science and Technology, 2006, 21 (6): 932-943 . 
    Abstract   PDF(459KB) ( 1406 )   Chinese Summary
    This paper introduces a new methodology that uses {\it knowledge structures}, a specific form of Kripke semantics for epistemic logic, to analyze communication protocols over hostile networks. The paper particularly focuses on automatic verification of authentication protocols. Our approach is based on the actual definitions of a protocol, not on some difficult-to-establish justifications. The proposed methodology is different from many previous approaches to automatic verification of security protocols in that it is justification-oriented instead of falsification-oriented, i.e., finding bugs in a protocol. The main idea is based on observations: separating a principal executing a run of protocol from the role in the protocol, and inferring a principal's knowledge from the local observations of the principal. And we show analytically and empirically that this model can be easily reduced to Satisfiability (SAT) problem and efficiently implemented by a modern SAT solver.
    References | Related Articles | Metrics
    Direct Model Checking Matrix Algorithm
    Zhi-Hong Tao, Hans Kleine Büning, and Li-Fu Wang
    Journal of Computer Science and Technology, 2006, 21 (6): 944-949 . 
    Abstract   PDF(324KB) ( 1224 )   Chinese Summary
    During the last decade, Model Checking has proven its efficacy and power in circuit design, network protocol analysis and bug hunting. Recent research on automatic verification has shown that no single model-checking technique has the edge over all others in all application areas. So, it is very difficult to determine which technique is the most suitable for a given model. It is thus sensible to apply different techniques to the same model. However, this is a very tedious and time-consuming task, for each algorithm uses its own description language. Applying Model Checking in software design and verification has been proved very difficult. Software architectures (SA) are engineering artifacts that provide high-level and abstract descriptions of complex software systems. In this paper a Direct Model Checking (DMC) method based on Kripke Structure and Matrix Algorithm is provided. Combined and integrated with domain specific software architecture description languages (ADLs), DMC can be used for computing consistency and other critical properties.
    References | Related Articles | Metrics
    A Note on the Stopping Redundancy of Linear Codes
    Shu-Tao Xia
    Journal of Computer Science and Technology, 2006, 21 (6): 950-951 . 
    Abstract   PDF(193KB) ( 1084 )   Chinese Summary
    In this paper, we study the stopping sets, stopping distance and stopping redundancy for binary linear codes. Stopping redundancy is a new concept proposed by Schwartz and Vardy recently for evaluating the performance of a linear code under iterative decoding over a binary erasure channel (BEC). Since the exact value of stopping redundancy is difficult to obtain in general, good lower and upper bounds are important. We obtain a new general upper bound on the stopping redundancy of binary linear codes which improves the corresponding results of Schwartz and Vardy.
    References | Related Articles | Metrics
    EAFoC: Enterprise Architecture Framework Based on Commonality
    Jin-Woo Kim, Ju-Hum Kwon, Young-Gab Kim, Chee-Yang Song, Hyun-Seok Kim, and Doo-Kwon Baik
    Journal of Computer Science and Technology, 2006, 21 (6): 952-964 . 
    Abstract   PDF(947KB) ( 1385 )   Chinese Summary
    The recent rapid development in information systems (ISs) has resulted in a critical need for integration and interoperability between heterogeneous ISs in various domains, using specific commonalities. However, stovepipe systems have been caused due to inconsistencies in planning IS architecture among stakeholders. So far, there has been no research on an enterprise architecture framework (EAF) that can satisfy with the coefficient factors of system architecture (SA) and enterprise architecture (EA). This paper proposes a new EAF that can resolve the problems inherent in existing legacy EAFs and their features. EAFoC (Enterprise Architecture Framework based on Commonality) is based on commonality that can be satisfied as the coefficient factors in both SA and EA within a common information technology (IT) domain. Thus, it should be possible to integrate an established heterogeneous framework for each stakeholder's view. Consequently, the most important contribution of this paper is to establish the appropriate EAFoC for the development of consistent IS architecture, smooth communication among stakeholders, systematic integration management of diversified and complicated new IT technologies, interoperability among heterogeneous ISs, and reusability based on commonality with other platforms.
    References | Related Articles | Metrics
    Code Based Analysis for Object-Oriented Systems
    Swapan Bhattacharya and Ananya Kanjilal
    Journal of Computer Science and Technology, 2006, 21 (6): 965-972 . 
    Abstract   PDF(349KB) ( 1437 )   Chinese Summary
    The basic features of object-oriented software makes it difficult to apply traditional testing methods in object-oriented systems. Control Flow Graph (CFG) is a well-known model used for identification of independent paths in procedural software. This paper highlights the problem of constructing CFG in object-oriented systems and proposes a new model named Extended Control Flow Graph (ECFG) for code based analysis of Object-Oriented (OO) software. ECFG is a layered CFG where nodes refer to methods rather than statements. A new metrics --- Extended Cyclomatic Complexity (E-CC) is developed which is analogous to McCabe's Cyclomatic Complexity (CC) and refers to the number of independent execution paths within the OO software. The different ways in which CFG's of individual methods are connected in an ECFG are presented and formulas for E-CC for these different cases are proposed. Finally we have considered an example in Java and based on its ECFG, applied these cases to arrive at the E-CC of the total system as well as proposed a methodology for calculating the basis set, i.e., the set of independent paths for the OO system that will help in creation of test cases for code testing.
    References | Related Articles | Metrics
    Improvement of Performance of MegaBlast Algorithm for DNA Sequence Alignment
    Guang-Ming Tan, Lin Xu, Dong-Bo Bu, Sheng-Zhong Feng, and Ning-Hui Sun
    Journal of Computer Science and Technology, 2006, 21 (6): 973-978 . 
    Abstract   PDF(361KB) ( 1405 )   Chinese Summary
    MegaBlast is one of the most important programs in NCBI BLAST (Basic Local Alignment Search Tool) toolkits. However, MegaBlast is computation and I/O intensive. It consumes a great deal of memory which is proportional to the size of the query sequences set and subject (database) sequences set of product. This paper proposes a new strategy for optimizing MegaBlast. The new strategy exchanges the query and subject sequences sets, and builds a hash table based on new subject sequences. It overlaps I/O with computation, shortens the overall time and reduces the cost of memory, since the memory here is only proportional to the size of subject sequences set. The optimized algorithm is suitable to be parallelized in cluster systems. The parallel algorithm uses query segmentation method. As our experiments shown, the parallel program which is implemented with MPI has fine scalability.
    References | Related Articles | Metrics
    A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States
    Jian-Liang Xu, Yun-Xia Liu, and Tsunehiro Yoshinaga
    Journal of Computer Science and Technology, 2006, 21 (6): 979-983 . 
    Abstract   PDF(272KB) ( 1242 )   Chinese Summary
    1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential (universal) states, and shows, for example, that for any function L(n) such that L(n)>=loglogn and L(n)=o(logn), the class of sets accepted by weakly (strongly) L(n) space-bounded 1-inkdot two-way alternating pushdown automata with only existential (universal) states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.
    References | Related Articles | Metrics
    Semi-Online Algorithms for Scheduling with Machine Cost
    Yi-Wei Jiang and Yong He
    Journal of Computer Science and Technology, 2006, 21 (6): 984-988 . 
    Abstract   PDF(287KB) ( 1434 )   Chinese Summary
    In this paper, we consider the following semi-online List Model problem with known total size. We are given a sequence of independent jobs with positive sizes, which must be assigned to be processed on machines. No machines are initially provided, and when a job is revealed the algorithm has the option to purchase new machines. By normalizing all job sizes and machine cost, we assume that the cost of purchasing one machine is 1. We further know the total size of all jobs in advance. The objective is to minimize the sum of the makespan and the number of machines to be purchased. Both non-preemptive and preemptive versions are considered. For the non-preemptive version, we present a new lower bound 6/5 which improves the known lower bound 1.161. For the preemptive version, we present an optimal semi-online algorithm with a competitive ratio of 1 in the case that the total size is not greater than 4, and an algorithm with a competitive ratio of 5/4 otherwise, while a lower bound 1.0957 is also presented for general case.
    References | Related Articles | Metrics
    Effective I/O Scheme Based on RTP for Multimedia Communication Systems
    Nam-Sup Park and Chong-Sun Hwang
    Journal of Computer Science and Technology, 2006, 21 (6): 989-996 . 
    Abstract   PDF(602KB) ( 1635 )   Chinese Summary
    The prime standard for audio/video transport in IP networks is the Real-time Transport Protocol (RTP), and it is targeted at useful services for the transport of real-time multimedia data. RTP was originally designed for use in multicast conferences, using the lightweight sessions model. RTP (in particular, the data part) is so tightly coupled to the application that a number of people have developed libraries that implement RTP. However, little is known about the RTP overheads between user area and kernel area within operating system. Actually, unnecessary copying between user area and kernel area lowers the system efficiency. In this paper, we present the design and implementation of Enhanced Multimedia Input/Output Scheme based on LINUX. We brought focus to the crossover architecture supporting RTP. Our contributions are able to be summarized into two components: 1) Enhanced Input/Output (EIO) scheme based on LINUX improves the transmission speed by reducing the overheads generated from data copy and context switch between user area and kernel area. And this enables server-based system to transport multimedia data more efficiently. 2) Furthermore, Enhanced Input/Output scheme with RTP (EIORTP) scheme supports efficient multimedia data transmission architecture. The two schemes improve the performance of massive multimedia data transmission.
    References | Related Articles | Metrics
    Inter-Cluster Routing Authentication for Ad Hoc Networks by a Hierarchical Key Scheme
    Yueh-Min Huang, Hua-Yi Lin, and Tzone-I Wang
    Journal of Computer Science and Technology, 2006, 21 (6): 997-011 . 
    Abstract   PDF(666KB) ( 1467 )   Chinese Summary
    Dissimilar to traditional networks, the features of mobile wireless devices that can actively form a network without any infrastructure mean that mobile {ad hoc} networks frequently display partition due to node mobility or link failures. These indicate that an ad hoc network is difficult to provide on-line access to a trusted authority server. Therefore, applying traditional Public Key Infrastructure (PKI) security framework to mobile ad hoc networks will cause insecurities. This study proposes a scalable and elastic key management scheme integrated into Cluster Based Secure Routing Protocol (CBSRP) to enhance security and non-repudiation of routing authentication, and introduces an ID-Based internal routing authentication scheme to enhance the routing performance in an internal cluster. Additionally, a method of performing routing authentication between internal and external clusters, as well as inter-cluster routing authentication, is developed. The proposed cluster-based key management scheme distributes trust to an aggregation of cluster heads using a threshold scheme faculty, provides Certificate Authority (CA) with a fault tolerance mechanism to prevent a single point of compromise or failure, and saves CA large repositories from maintaining member certificates, making ad hoc networks robust to malicious behaviors and suitable for numerous mobile devices.
    References | Related Articles | Metrics
    Parallel Switch System with QoS Guarantee for Real-Time Traffic
    Wen-Jie Li, Bin Liu, Yang Xu, and Heng Liao
    Journal of Computer Science and Technology, 2006, 21 (6): 1012-1021 . 
    Abstract   PDF(477KB) ( 1540 )   Chinese Summary
    This paper studies the load-balancing algorithm and quality of service (QoS) control mechanism in a 320Gb/s switch system, which incorporates four packet-level parallel switch planes. Eight priorities for both unicast and multicast traffic are implemented, and the highest priority with strict QoS guarantee is designed for real-time traffic. Through performance analysis under multi-priority burst traffic, we demonstrate that the load-balancing algorithm is efficient, and the switch system not only provides excellent performance to real-time traffic, but also efficiently allocates bandwidth among other traffic of lower priorities. As a result, this parallel switch system is more scalable towards next generation core routers with QoS guarantee, as well as ensures in-order delivery of IP packets.
    References | Related Articles | Metrics
    Design and Analysis of a Multiscale Active Queue Management Scheme
    Qi-Jin Ji and Yong-Qiang Dong
    Journal of Computer Science and Technology, 2006, 21 (6): 1022-1030 . 
    Abstract   PDF(523KB) ( 1224 )   Chinese Summary
    Since Internet is dominated by TCP-based applications, active queue management (AQM) is considered as an effective way for congestion control. However, most AQM schemes suffer obvious performance degradation with dynamic traffic. Extensive measurements found that Internet traffic is extremely bursty and possibly self-similar. We propose in this paper a new AQM scheme called multiscale controller (MSC) based on the understanding of traffic burstiness in multiple time scale. Different from most of other AQM schemes, MSC combines rate-based and queue-based control in two time scales. While the rate-based dropping on burst level (large time scales) determines the packet drop aggressiveness and is responsible for low and stable queuing delay, good robustness and responsiveness, the queue-based modulation of the packet drop probability on packet level (small time scales) will bring low loss and high throughput. Stability analysis is performed based on a fluid-flow model of the TCP/MSC congestion control system and simulation results show that MSC outperforms many of the current AQM schemes.
    References | Related Articles | Metrics
    Bandwidth Reservation Using Velocity and Handoff Statistics for Cellular Networks
    Chuan-Lin Zhang, Kam Yiu Lam, and Wei-Jia Jia
    Journal of Computer Science and Technology, 2006, 21 (6): 1031-1039 . 
    Abstract   PDF(452KB) ( 1247 )   Chinese Summary
    The percentages of blocking and forced termination rates as parameters representing quality of services (QoS) requirements are presented. The relation between the connection statistics of mobile users in a cell and the handoff number and new call number in next duration in each cell is explored. Based on the relation, statistic reservation tactics are raised. The amount of bandwidth for new calls and handoffs of each cell in next period is determined by using the strategy. Using this method can guarantee the communication system suits mobile connection request dynamic. The QoS parameters: forced termination rate and blocking rate can be maintained steadily though they may change with the offered load. Some numerical experiments demonstrate this is a practical method with affordable overhead.
    References | Related Articles | Metrics
  Journal Online
Just Accepted
Top Cited Papers
Top 30 Most Read
Paper Lists of Areas
Special Issues
   ScholarOne Manuscripts
   Log In

User ID:


  Forgot your password?

Enter your e-mail address to receive your account information.

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved