Catálogo de publicaciones - libros

For path planning, an optimal path is defined both by its length and by its clearance from obstacles. Many motion planning techniques such as the roadmap method, the cell decomposition method, and the potential field method generate low quality paths with redundant motions which are post-processed to generate high quality approximations of the optimal path. In this paper, we present a (( + )) algorithm to optimize a path between a source and a destination in a plane based on a preset clearance from obstacles and overall length, where is a multiple of the number of vertices on the given path, is a multiple of the number of obstacle vertices, and is the average number of obstacle edges against which the clearance check is done for each of the () queries to determine whether a potential edge of the path is collision-free. This improves the running time of the geometric algorithm presented by Bhattacharya and Gavrilova (2007) which already generates a high quality approximation of the optimal path.

Next generation of GIS software should be able to manipulate and analyse complex situations of real world phenomena. One of the desired components in such software or system is the geometric modeling that works with 3D spatial operations. This paper presents a portion of problem that we currently attempt to solve, that is the 3D spatial operations for Geo DBMS. Some popular spatial operations in 3D GIS for example 3D XOR, 3D union, 3D intersection, and 3D difference are vital for 3D spatial analysis and forms major discussion of this paper and part of our research effort to address the 3D GIS problem. To formulate this research in a suitable way, our approach is to develop the new 3D data type, polyhedron, within geo-DBMS. The basic idea is to relate the implementation of intersection point in 3D planar polygon (Chen and Abdul-Rahman, 2006) into the geometrical modeling for 3D spatial operations. The approach works and we highlighted the results by using the real world data sets. The research shows that the essential mathematical algorithms are applicable for real world objects and provides a solution towards a full 3D analytical operation in future.

Today, flash memory is widely used for various kinds of products. Unlike a hard disk, it has neither mechanical parts nor seek-delay. Therefore, a user may expect steady performance under disk fragmentation in flash storage. However, most commercial products do not satisfy this expectation. For example, a SDMMC card can be written in 18.7Mbytes/sec speed sequentially, but its write speed is slowed down to 3.2Mbytes/sec when it is seriously fragmented. It is only 18% of the original performance.

In this paper, we analyze the reason for performance degradation in a flash disk, and propose an FTL level optimization technique, named , to lessen the fragmentation effect. We applied the technique to the Log-block FTL algorithm and showed that it can enhance write performance by 150% in a severely fragmented flash disk.

Using the standard Object-based Storage Device, OASIS has been developed as a cluster filesystem. Like the most of existing out-of-band cluster filesystems using ODSs, the OASIS could not support the extended remove UNIX semantics to defer the remove of an inode until the uses of the inode in all client nodes are finished. This nonsupport generates the problems that it does not protect users to make use of the deleted inode and does share an inode of a deleted directory entry with a newly created entry, which is due to client node’s VFS to support the remove UNIX semantics. To resolve these problems, this paper proposes the re-designed OASIS to perform an inode deletion until its uses are finished by extending the existing lock table for cache coherence. The suggested approach can support the remove UNIX semantics in the distributed environment and easily be adopted in the existing out-of-band cluster filesystems if using their locking mechanism.

Some index structures have been redesigned to minimize the cache misses and improve their CPU cache performances. The Cache Sensitive B+-Tree and recently developed Cache Sensitive T-Tree are the most well-known cache conscious index structures. Their performance evaluations, however, were made in single core CPU machines. Nowadays even the desktop computers are equipped with multi-core CPU processors. In this paper, we present an experimental performance study to show how cache conscious trees perform on different types of CPU processors that are available in the market these days.

This paper presents new page replacement algorithms for NAND flash memory, called CFLRU/C, CFLRU/E, and DL-CFLRU/E. The algorithms aim at reducing the number of erase operations and improving the wear-leveling degree of flash memory. In the CFLRU/C and CFLRU/E algorithms, the least recently used clean page is selected as the victim within the pre-specified window of the LRU list. If there is no clean page within the window, CFLRU/C evicts the dirty page with the lowest access frequency while CFLRU/E evicts the dirty page with the lowest block erase count. DL-CFLRU/E maintains two LRU lists called the clean page list and the dirty page list, and first evicts a page from the clean page list. If there is no clean page in the clean page list, DL-CFLRU/E evicts the dirty page with the lowest block erase count within the window of the dirty page list. Experiments through simulation studies show that the proposed algorithms reduce the number of erase operations and improve the wear-leveling degree of flash memory compared to LRU and CFLRU.

Mobile computing devices use flash memory as a secondary storage because it has many attractive features such as small size, fast access speeds, shock resistance, and light weight. Mobile computing devices exploit a swap system to extend a limited main memory space and use flash memory as a swap system. Although flash memory has the attractive features, it should perform garbage collection, which includes erase operations. The erase operations are very slow, and usually decrease the performance of the system. Besides, the number of the erase operations allowed to each block is also limited. To minimize the garbage collection time and evenly wear out, our proposed garbage collection policy focuses on minimizing the garbage collection time and wear-leveling. Trace-driven simulations show that the proposed policy performs better than existing garbage collection policies in terms of the number of erase operation, the garbage collection time, total amount of energy consumption and the endurance of flash memory.

Most of the mobile devices are equipped with NAND flash memories even if it has characteristics of not-in-place update and asymmetric I/O latencies among read, write, and erase operations: a write/erase operation is much slower than a read operation in a flash memory. For the overall performance of a flash memory system, the buffer replacement policy should consider the above severely asymmetric I/O latencies. Existing buffer replacement algorithms such as LRU, LIRS, and ARC cannot deal with the above problems. This paper proposes an add-on buffer replacement policy that enhances LIRS by reordering writes of not-cold dirty pages from the buffer cache to flash storage. The enhances LIRS-WSR algorithm focuses on reducing the number of write/erase operations as well as preventing serious degradation of buffer hit ratio. The trace-driven simulation results show that, among the existing buffer replacement algorithms including LRU, CF-LRU, ARC, and LIRS, our LIRS-WSR is best in almost cases for flash storage systems.

In this work, we develop novel file system, FRASH, for byte-addressable NVRAM (FRAM[1]) and NAND Flash device. Byte addressable NVRAM and NAND Flash is typified by the DRAM-like fast access latency and high storage density, respectively. Hierarchical storage architecture which consists of byte-addressable NVRAM and NAND Flash device can bring synergy and can greatly enhance the efficiency of file system in various aspects. Unfortunately, current state of art file system for Flash device is not designed for byte-addressable NVRAM with DRAM-like access latency. FRASH file system (File System for FRAM an NAND Flash) aims at exploiting physical characteristics of FRAM and NAND Flash device. It effectively resolves long mount time issue which has long been problem in legacy LFS style NAND Flash file system. In FRASH file system, NVRAM is mapped into memory address space and contains file system metadata and file metadata information. Consistency between metadata in NVRAM and data in NAND Flash is maintained via transaction. In hardware aspect, we successfully developed hierarchical storage architecture. We used 8 MByte FRAM which is the largest chip allowed by current state of art technology. We compare the performance of FRASH with legacy Its-style file system for NAND Flash. FRASH file system achieves x5 improvement in file system mount latency.

Cost-effectiveness is one of the most critical factors in the development of low-end embedded systems. The use of a compressed filesystem is a simple but effective solution for achieving such cost-effectiveness. However, since conventional compressed filesystems are designed for disk-like devices and relatively abundant computing resources, they are not suitable for low-end embedded systems with small amount of memory and NAND flash-based storage. This paper presents a memory-efficient compressed filesystem designed for low-end embedded systems and NAND flash memory. Experiments by prototype implementation show that the proposed filesystem outperforms conventional ones in terms of memory-efficiency and I/O performance.