Browsing by Author "Lee, Ming-Chang"

Now showing 1 - 11 of 11

Adaptive Write Interference Management with Efficient Mapping for Shingled Recording Disks
(2019-01-01)
Lee, Ming-Chang
;
Chang, Li-Pin
;
Wu, Sung-Ming
;
Yui, Wei-Shang
;
資訊工程學系
Shingled Magnetic Recording (SMR) is a novel disk technology that partially overlaps adjacent disk tracks for high storage density. The partial overlap creates write interference between tracks, and overwriting a track requires to rewrite all its downstream tracks. Inspired by the highly unequal track modify probabilities under real workloads, we propose moving frequently modified tracks toward a downstream, deliberately reserved track, called a guard track, to reduce the extent of write interference. We also introduce a low-cost, seek-optimized scheme for efficient logical-to-physical address mapping. Experimental results showed that our approach outperformed a popular design by 54% and 55% on average in terms of write response time and total disk writes, respectively.
Cache Replacement Algorithms for YouTube
(2014-01-01)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
In recent years, many social network systems like, YouTube, Facebook, Twitter, etc. have been a part of our everyday life. Among these systems, YouTube which plays video programs of different interesting themes for users has been one of the most attractive ones. Basically, when the space of Memcached in YouTube is full, the Least Recently Used algorithm (LRU for short) is employed to evict a least recently watched video. However, the LRU, due to its own property, may cause more miss counts of Memcached for YouTube, consequently increasing the network bandwidth and energy consumptions. To solve these problems, in this paper we proposed two cache replacement algorithms, the Pareto Least Recently Used algorithm (PLRU for short) and Pareto Least Frequently Used algorithm (PLFU for short), in which videos are classified into different popularity categories, and those videos in the top 10% and 20% of the top two popular categories of YouTube, based on Pareto principle, are then chosen to serve users\' requests without removing them from Memcached. The simulation results show that the PLFU algorithm can significantly reduce miss counts of Memcached compared with those when the LRU and Least Frequently Used algorithm (LFU for short) are employed, thus achieving great performance improvements for the top two popular categories of videos. Also, when a large space of Memcached is available, the miss counts of the PLRU are higher than those of the LRU. But when comparing them in a small available Memcached space, the miss counts of the LRU on the contrary is higher than those of the PLRU.
Characterization of Silicon Photonics Modulator Integration and High Efficiency Testing Platform
(2019-01-01)
Chen, Shang-Chun
;
Wun, Sin-Jhu
;
Hsu, Chih-Hsiang
;
Lin, Chen-Yu
;
Zhang, Jie
We successfully establish a silicon photonics device manufacturing and testing platform in 200mm SOI wafer. We integrate modulator and driver chip to show 30Gbis PAM4 capability. A fully-automatic wafer level characterization process is built up for all optical devices in surface coupling method.
Deriving Job Completion Reliability and Job Energy Consumption for a General MapReduce Infrastructure from Single-Job Perspective
(2013)
Lin, Jia-Chun
;
Leu, Fang-Yie
;
Lee, Ming-Chang
;
Chen, Ying-ping
;
資訊工程學系
MapReduce as a master-slave infrastructure consists of two master-side severs and a large number of slave-side working nodes. In this paper, we derive a job completion reliability (JCR for short) model from a single-job perspective for a general MapReduce infrastructure in which no redundancy scheme is adopted on the master side, and a cold-standby scheme is employed on the slave side. Without loss of generality, the JCR model is derived based on a Poisson distribution. In addition, we calculate the corresponding job energy consumption (JEC for short). Through the simulation and analytical results, MapReduce managers and service providers can comprehend how this infrastructure behaves and how to improve the infrastructure so as to achieve a more reliable and energy-efficient MapReduce environment.
Developing a Performance-analysis Model for a Star-Topology Data Grid from Multi-User Perspective
(2014)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Data grids often integrate many geographically dispersed storage and computational resources to provide users with an environment in which scientists and scientific researchers can execute their large-scale applications and store their data collected from other databases or produced by their experiments. To efficiently transfer a huge volume of data shared by users among the clusters or nodes in data grids, several co-allocation schemes have been proposed to shorten the data delivery. In this paper, we develop a performance-analysis model, named the Response Time Evaluation Model (RTEM for short), over a topology reduced from a tree to a star to evaluate data grid co-allocation schemes from multi-user perspective.
Hybrid Job-Driven Scheduling for Virtual MapReduce Clusters
(2016-06)
Lee, Ming-Chang
;
Lin, Jia-Chun
;
Yahyapour, Ramin
;
資訊工程學系
;
Department of Computer Science
It is cost-efficient for a tenant with a limited budget to establish a virtual MapReduce cluster by renting multiple virtual private servers (VPSs) from a VPS provider. To provide an appropriate scheduling scheme for this type of computing environment, we propose in this paper a hybrid job-driven scheduling scheme (JoSS for short) from a tenant\'s perspective. JoSS provides not only job-level scheduling, but also map-task level scheduling and reduce-task level scheduling. JoSS classifies MapReduce jobs based on job scale and job type and designs an appropriate scheduling policy to schedule each class of jobs. The goal is to improve data locality for both map tasks and reduce tasks, avoid job starvation, and improve job execution performance. Two variations of JoSS are further introduced to separately achieve a better map-data locality and a faster task assignment. We conduct extensive experiments to evaluate and compare the two variations with current scheduling algorithms supported by Hadoop. The results show that the two variations outperform the other tested algorithms in terms of map-data locality, reduce-data locality, and network overhead without incurring significant overhead. In addition, the two variations are separately suitable for different MapReduce-workload scenarios and provide the best job performance among all tested algorithms.
Pareto-based cache replacement for YouTube
(2015-11-01)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Recently, YouTube, which plays diverse video programs for worldwide users, has been one of the most attractive social-networking systems. YouTube employs a distributed memory caching system called Memcached to cache videos, and utilizes the Least Recently Used algorithm (LRU for short) to evict the least recently watched video when Memcached runs out of space. However, LRU may cause a high miss count, which is the number of times that a video requested by users cannot be found in Memcached. This might not only increase network overhead, but also cause a poor service quality for YouTube since those videos need to be retrieved from the remote back-end database. To solve these problems, in this paper, we classify videos into popular and unpopular videos and propose two cache replacement algorithms based on the Pareto principle. One is Pareto-based Least Frequently Used algorithm (PLFU for short), and the other is Pareto-based Least Recently Used algorithm (PLRU for short). The two algorithms always keep several top popular videos of each video category in Memcached to reduce miss count. However, when Memcached has insufficient space to hold a video requested by a user, PLFU and PLRU repeatedly evicts an unpopular video from Memcached based on LFU and LRU so as to hold the video. Our simulation results based on a real-world YouTube trace show that PLFU performs the best among all tested algorithms in terms of miss count and video-retrieval time. The results also indicate that when PLRU is used for a longer time, it provides the second best performance.
PFRF: An adaptive data replication algorithm based on star-topology data grids
(2012-07-01)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
Recently, data replication algorithms have been widely employed in data grids to replicate frequently accessed data to appropriate sites. The purposes are shortening file transmission distance and delivering files from nearby sites to local sites so as to improve data access performance and reduce bandwidth consumption. Some of the algorithms were designed based on unlimited storage. However, they might not be practical in real-world data grids since currently no system has infinite storage. Others were implemented on limited storage environments, but none of them considers data access patterns which reflect the changes of users' interests, and these are important parameters affecting file retrieval efficiency and bandwidth consumption. In this paper, we propose an adaptive data replication algorithm, called the Popular File Replicate First algorithm (PFRF for short), which is developed on a star-topology data grid with limited storage space based on aggregated information on previous file accesses. The PFRF periodically calculates file access popularity to track the variation of users' access behaviors, and then replicates popular files to appropriate sites to adapt to the variation. We employ several types of file access behaviors, including Zipf-like, geometric, and uniform distributions, to evaluate PFRF. The simulation results show that PFRF can effectively improve average job turnaround time, bandwidth consumption for data delivery, and data availability as compared with those of the tested algorithms. (C) 2011 Elsevier B.V. All rights reserved.
ReMBF: A Reliable Multicast Brute-Force Co-Allocation Scheme for Multi-user Data Grids
(2015)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
In this paper we propose a novel co-allocation scheme, called a Reliable Multicast Brute-Force co-allocation scheme (ReMBF for short), which employs a reliable multicast (RM for short) technique with the Brute-Force (BF for short) scheme to accelerate data retrieval and delivery, and reliably transmit data to its users for data grids. Several types of data access patterns, including Zipf-like, geometric, and uniform distributions, are utilized to model user access behaviors and evaluate the performance of ReMBF. The simulation results demonstrate that ReMBF can efficiently deliver a bulk of data in a shorter time period compared with two state-of-the-art schemes.
Scheduling MapReduce Tasks on Virtual MapReduce Clusters from a Tenant\'s Perspective
(2014)
Lin, Jia-Chun
;
Lee, Ming-Chang
;
Yahyapour, Ramin
;
資訊工程學系
;
Department of Computer Science
Renting a set of virtual private servers (VPSs for short) from a VPS provider to establish a virtual MapReduce cluster is cost-efficient for a company/organization. To shorten job turnaround time and keep data locality as high as possible in this type of environment, this paper proposes a Best-Fit Task Scheduling scheme (BFTS for short) from a tenant\'s perspective. BFTS schedules each map task to a VPS that can finish the task earlier than the other VPSs by predicting and comparing the time required by every VPS to retrieve the map-input data, executeTS sch the map task, and become idle in an online manner. Furthermore, BFedules each reduce task to a VPS that is close to most VPSs that execute the related map tasks. We conduct extensive experiments to compare BFTS with several scheduling algorithms employed by Hadoop. The experimental results show that BFTS is better than the other tested algorithms in terms of map-data locality, reduce-data locality, and job turnaround time. The overhead incurred by BFTS is also evaluated, which is inevitable but acceptable compared with the other algorithms.
TSR: Topology Reduction from Tree to Star Data Grids
(2013)
Lee, Ming-Chang
;
Leu, Fang-Yie
;
Chen, Ying-ping
;
資訊工程學系
;
Department of Computer Science
To speed up data transmission of data grids, several co-allocation schemes have been proposed. However, data grids are often large in scale, heterogeneous in participating resources, and complicated in architecture and network topology, consequently increasing the analytical complexity of its data transmission behaviour. In other words, if we can reduce the data transmission topology for the grid, the analysis will be easier. Therefore, in this paper, we propose a topology reduction approach, called the Tree-to-Star Reduction method (TSR for short), which can reduce a packet delivery tree topology to a star for a data grid so that the data transmission of a co-allocation scheme can be more conveniently analyzed. Here, a delivery tree topology, as a tree topology rooted at the destination node, is a network topology for delivering all fragments of a file to the destination node.