學術出版;;Publications

Permanent URI for this communityhdl:11536/1

收集所有交通大學研究人員與學生個人或團體所發表之各項學術著作，涵蓋期刊論文、教師專書、學位論文等項。;;Collections of Publications of NCTU Researchers and Students Like Journal Papers and Thesis.

Browse

🏛️國立陽明交通大學機構典藏

Search Results

Now showing 1 - 10 of 26

Classifying and alleviating the communication overheads in matrix computations on large-scale NUMA multiprocessors
(1998-12-01)
Wang, YM
;
Wang, HH
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Large-scale, shared-memory multiprocessors have non-uniform memory access (NUMA) costs. The high communication cost dominates the source of matrix computations' execution. Memory contention and remote memory access are two major communication overheads on large-scale NUMA multiprocessors. However, previous experiments and discussions focus either on reducing the number of remote memory accesses or on alleviating memory contention overhead. In this paper, we propose a simple but effective processor allocation policy, called rectangular processor allocation, to alleviate both overheads at the same time. The policy divides the matrix elements into a certain number of rectangular blocks, and assigns each processor to compute the results of one rectangular block. This methodology may reduce a lot of unnecessary memory accesses to the memory modules. After running many matrix computations under a realistic memory system simulator, we confirmed that at least one-fourth of the communication overhead map be reduced. Therefore, we conclude that rectangular processor allocation policy performs better than other popular policies, and that the combination of rectangular processor allocation policy with software interleaving data allocation policy is a better choice to alleviate communication overhead. (C) 1998 Elsevier Science Inc. All rights reserved.
Using data clustering to improve cleaning performance for flash memory
(1999-03-01)
Chiang, ML
;
Lee, PCH
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Flash memory offers attractive features for storage of data, such as non-volatility, shock resistance, fast access speed, and low power consumption. However, it requires erasing before it can be overwritten. The erase operations are slow and consume comparatively a great deal of power, Furthermore, flash memory can only be Erased a limited number of times. To overcome hardware limitations, we use the non-in-place update mechanism that requires a cleaner to reclaim space occupied by obsolete data. To improve cleaning performance and prolong hash memory lifetime, we propose a new data reorganization method. By this method, data in flash memory are dynamically classified and clustered together according to their accessing frequencies, Experimental results show that this clustering technique significantly improved the cleaning performance for a variety of cleaning algorithms. The number of erase operations performed is greatly reduced and flash memory lifetime is prolonged. Even wearing is ensured as well, Copyright (C) 1999 John Wiley & Sons, Ltd.
An implementation of using remote memory to checkpoint processes
(1999-09-01)
Hsu, ST
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Process checkpointing is a procedure which periodically saves the process states into stable storage. Most checkpointing facilities select hard disks for archiving. However, the disk seek time is limited by the speed of the read-write heads, thus checkpointing process into a local disk requires extensive disk bandwidth. In this paper, we propose an approach that exploits the memory on idle workstations as a faster storage for checkpointing. In our scheme, autonomous machines which submit jobs to the computation server offer their physical memory to the server for job checkpointing. Eight applications are used to measure the remote memory performance in four checkpointing policies. Experimental results show that remote memory reduces at least 34.5 per cent of the overhead for sequential checkpointing and 32.1 per cent for incremental checkpointing. Additionally, to checkpoint a running process into a remote memory requires only 60 per cent of the local disk checkpoint latency time. Copyright (C) 1999 John Wiley & Sons, Ltd.
Cleaning policies in mobile computers using flash memory
(1999-11-01)
Chiang, ML
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Flash memory is small, lightweight, shock-resistant, nonvolatile, and consumes little power. Flash memory therefore shows promise for use in storage devices for consumer electronics, mobile computers and embedded systems. However, flash memory cannot be overwritten unless erased in advance. Erase operations are slow that usually decrease system performance, and consume power. The number of erase cycles is also limited. For power conservation, better system performance, and longer flash memory lifetime, system support for erasure management is necessary. In this paper, we use the non-update-in-place scheme to implement a flash memory server and propose a new cleaning policy to reduce the number of erase operations needed and to evenly wear out flash memory. The policy uses a fine-grained method to effectively cluster hot data and cold data in order to reduce cleaning overhead. A wear-leveling algorithm is also proposed. Performance evaluations show that erase operations are significantly reduced and flash memory is evenly worn, Though the proposed fine-grained separation scheme is targeted at flash memory-based systems, it can be applied to other storage systems as well. (C) 1999 Elsevier Science Inc. All rights reserved.
Adaptive-level memory caches on World Wide Web servers
(2000-03-01)
Chang, DW
;
Ke, HR
;
Chang, RC
;
交大名義發表
;
資訊工程學系
Owing to the fast growth of World Wide Web (WWW), web traffic has become a major component of Internet traffics. Consequently, the reduction of document retrieval latency on WWW becomes more and more important. The latency can be reduced in two ways: reduction of network delay and improvement of web servers' throughput. Our research aims at improving a web server's throughput by keeping a memory cache in a web server's address space. In this paper, we focus on the design and implementation of a memory cache scheme. We propose a novel web cache management policy named the adaptive-level policy that either caches the whole file content or only a portion of it, according to the file size. The experimental results show three things. First, our memory cache is beneficial since, under our experimental workloads, the throughput improvement can achieve 32.7%. Second, our cache management policy is suitable for current web traffic. Third, with the increasing popularity of multimedia files, our policy will outperform others currently used in WWW. (C) 2000 Elsevier Science B.V. All rights reserved.
Real-time disk scheduling for multimedia applications with deadline-modification-scan scheme
(2000-09-01)
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Real-time disk scheduling (RTDS) is important for time-critical multimedia applications. In conventional approaches of real-time disk scheduling, such as SCAN-EDF, the seek-optimizing SCAN scheme is applied to reduce the disk service time of the real-time EDF schedule. Since only tasks with the same deadline are seek-optimized, the obtained improvement of SCAN-EDF is limited. In this paper, based on the maximum-scannable-group (MSG) concept, a deadline-modification-scan (DMS or DM-SCAN) algorithm is proposed. Our algorithm uses MSG to automatically decide the suitable task groups for seek-optimizing. Based on the MSG concept, we repeatedly apply DMS to further increase disk throughput to support more tasks. We have implemented the proposed algorithm on UnixWare 2.01. The appropriate problem behaviors and parameter values to yield good solutions are investigated. Experiments show that DMS is better than conventional approaches in both the obtained disk throughput and the supported tasks. Moreover, our proposed approach can schedule task sets that are not schedulable by EDF and SCAN-EDF.
Hierarchical loop scheduling for clustered NUMA machines
(2000-12-01)
Wang, YM
;
Wang, HH
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
Loop scheduling is an important issue in the development of high performance multiprocessors. As modern multiprocessors have high and non-uniform memory access (NUMA) costs, the communication costs dominate the execution of parallel programs. Previous affinity algorithms perform better than dynamic algorithms under non-clustered NUMA multiprocessors, but they suffer heavy overheads when migrating work load under clustered NUMA machines. In this paper, we propose a new loop scheduling policy, hierarchical policy, to improve Various affinity scheduling algorithms (AFSs) for clustered NUMA machines. We cyclically distribute the iteration chunks to clusters. When imbalance occurs, the migration of iterations is carried on hierarchically. We use hierarchical policy to improve AFS and modified AFS (MAFS), and we call them Hierarchical AFS (HAFS) and Hierarchical MAFS (HMAFS), respectively. AFS uses a deterministic assignment policy to assign repeated executions of loop iteration to the same processor. MAFS modifies the migration policy of AFS, and reduces the number of synchronization operations. We confirm our idea by running many applications under a clustered NUMA simulator. Our experimental result shows that hierarchical policy reduces the inter-cluster remote memory accesses, decreases the locks to the queues, and effectively balances the work load. We also show that HMAFS is the best choice among these algorithms in most cases. (C) 2000 Elsevier Science Inc. All rights reserved.
EJVM: an economic Java run-time environment for embedded devices
(2001-02-01)
Chang, DW
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
As network-enabled embedded devices and Java grow in their popularity, embedded system researchers start seeking ways to make these devices Java-enabled. However, it is a challenge to apply Java technology to these devices due to their shortage of resources. In this paper, we propose EJVM (Economic Java Virtual Machine), an economic way to run Java programs on network-enabled and resource-limited embedded devices. Espousing the architecture proposed by distributed JVM, we store all Java codes on the server to reduce the storage needs of the client devices. In addition, we use two novel techniques to reduce the client-side memory footprints: server-side class representation conversion and on-demand bytecode loading. Finally, we maintain client-side caches and provide performance evaluation on different caching policies. We implement EJVM by modifying a freely available JVM implementation, Kaffe. From the experiment results, we show that EJVM can reduce Java heap requirements by about 20-50 % and achieve 90 % of the original performance. Copyright (C) 2001 John Wiley & Sons, Ltd.
Reschedulable-Group-SCAN scheme for mixed real-time/non-real-time disk scheduling in a multimedia system
(2001-11-15)
Chang, HP
;
Chang, RI
;
Shih, WK
;
Chang, RC
;
資訊工程學系
Real-time disk scheduling is important for time-critical multimedia applications. Previous approaches, such as SCAN-earliest deadline first (EDF) or DM-SCAN, applied the SCAN scheme to reschedule service sequence of input tasks to reduce tasks' service time. However, they required the input to be in EDF order. In DM-SCAN, a deadline modification scheme was employed to obtain a pseudo-EDF sequence from non-EDF ordered input tasks. Because the modified deadlines were smaller than the original ones, number of tasks that could be rescheduled is decreased and thus data throughput is reduced. In this paper, we propose Reschedulable-Group-SCAN (RG-SCAN), a new real-time disk scheduling algorithm using the concept of Reschedulable-Group (R-Group). Differing from previous approaches, RG-SCAN has no limitation on the input task's sequence. In addition, by exploiting the service time's reduction after rescheduling in each R-Group, RG-SCAN has been extended to serve mixed real-time and non-real-time workloads. As shown in experimental results. our approach can support more tasks than DM-SCAN, both real-time and non-real-time. Additionally, our approach can provide larger data throughput and offer better response time to non-real-time tasks. For example, given 30 random-generated real-time tasks, the number of non-real-time tasks that can be supported by RG-SCAN is 1.3 times that supported by DM-SCAN. In addition, our data throughput is 1.1 times DM-SCAN's. (C) 2001 Elsevier Science Inc. All rights reserved.
An efficient and stable ray tracing algorithm for parametric surfaces
(2002-07-01)
Wang, SW
;
Shih, ZC
;
Chang, RC
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose an efficient and stable algorithm for finding the ray-surface intersections. Newton's method and Bezier clipping are adapted to form the core of our algorithm. Ray coherence is used to find starting points for Newton iteration. We introduce an obstruction detection technique to verify whether an intersection point found by using Newton's method is the closest one. When Newton's method fails to achieve convergence, we use Bezier clipping as the substitution to find the intersection points. This combination achieves significant improvement in tracing primary rays. A similar approach also successfully improves the performance in tracing secondary rays.

學術出版;;Publications

Browse

Filters

Settings

Sort By

Results per page

🏛️國立陽明交通大學機構典藏

Search Results