An Efficient Merging Algorithm for Recovery and Garbage Collection in Incremental Checkpointing

허준영,이상호,홍지만,조유근 朝鮮大學校 電子情報通信硏究所 2003 電子情報通信硏究所論文誌 Vol.6 No.2

Incremental checkpointing saves only the modified pages of the checkpoint using page write-protection. While on the one hand, the checkpointing overhead is decreased when incremental checkpointing is used, old checkpoints cannot be merged and deleted because the process' memory pages become spread out over many incremental checkpoints. In this paper, we present an efficient merging algorithm for the recovery and garbage collection in incremental checkpointing. The proposed algorithm can merge several incremental checkpoints into a full checkpoint for recovery and can delete unnecessary incremental checkpoints.

Optimal Checkpoint Times for a Computer System with Hardware and Software Failures

Kenichiro Naruse,Toshio Nakagawa 대한산업공학회 2015 대한산업공학회 추계학술대회논문집 Vol.2015 No.11

Tasks with random processing times of a computer system are executed successively. Checkpoint methods can be placed at the end of tasks. Two types of checkpoints are called Journal Checkpoint (JC) and Flush Checkpoint (FC) where JC needs a small time compared with FC to store checkpoint data, and FC needs a long time compared with JC to store checkpoint data. The problem is that in what places we set suitable checkpoints. The mean execution times per one task are obtained and optimal numbers which minimize them are derived analytically and numerically.

RM 스케줄링된 실시간 태스크에서의 최적 체크 포인터 구간 선정

郭成祐(Seong-Woo Kwak),鄭容朱(Young-Joo Jung) 대한전기학회 2007 전기학회논문지 Vol.56 No.6

For a system with multiple real-time tasks of different deadlines, it is very difficult to find the optimal checkpoint interval because of the complexity in considering the scheduling of tasks. In this paper, we determine the optimal checkpoint interval for multiple real-time tasks that are scheduled by RM(Rate Monotonic) algorithm. Faults are assumed to occur with Poisson distribution. Checkpoints are inserted in the execution of task with equal distance in the same task, but different distances in other tasks. When faults occur, rollback to the latest checkpoint and re-execute task after the checkpoint. We derive the equation of maximum slack time for each task, and determine the number of re-executable checkpoint intervals for fault recovery. The equation to check the schedulibility of tasks is also derived. Based on these equations, we find the probability of all tasks executed within their deadlines successfully. Checkpoint intervals which make the probability maximum is the optimal.

Functional Analysis of the Putative BUB2 Homologues of C. elegans in the Spindle Position Checkpoint

Lee, Kyung-Hee,Song, Ki-Won The Korean Society for Integrative Biology 2005 Integrative biosciences Vol.9 No.2

Spindle position checkpoint monitors the orientation of mitotic spindle for proper segregation of replicated chromosomes into mother cell and the daughter, and prohibits mitotic exit when mitotic spindle is misaligned. BUB2 forms one of the key upstream element of spindle position checkpoint in budding yeast, but its functional homologues have not been identified in higher eukaryotes. Here, we analyzed the functions of two putative BUB2 homologues of C. elegans in the spindle orientation checkpoint. From the C. elegans genome database, we found that two open reading frames (ORFs), F35H12_2 and C33F10_2, showed high sequence homology with BUB2. We obtained the expressed sequence tag (EST) clones for F35H12_2 (yk221d4) and C33F10_2 (yk14e10) and verified the full cDNA for each ORF by sequencing and 5' RACE with SL1 primer. The functional complementation assays of yk221d4 and yk14e10 in ${\Delta}bub2$ of S. cerevisiae revealed that these putative BUB2 homologues of C. elegans could not replace the function of BUB2 in spindle position checkpoint and mitotic exit. Our attempt to document the component of spindle position checkpoint in metazoans using sequence homology was not successful. This suggests that structural information about its components might be required to identify functional homologues of the spindle position checkpoint in higher eukaryotes.

안정 저장장치의 효율적 사용을 위한 페이지 기반 점진적 검사점 기법

허준영(Junyoung Heo),이상호(Sangho Yi),구본철(Boncheol Gu),조유근(Yookun Cho),홍지만(Jiman Hong) 한국정보과학회 2007 정보과학회논문지 : 시스템 및 이론 Vol.34 No.11·12

페이지 기반 점진적 검사점은 검사점 오버헤드를 줄이기 위해 프로세스의 메모리 상태 중 변경된 페이지만 저장하는 기법이다. 그러나 점진적 검사점의 누적 크기는 검사점 횟수가 증가함에 따라 서서히 증가하게 된다. 이는 한 페이지가 검사점 작성 이후에 변경되어 검사점 작성시에 검사점에 저장되는 과정이 되풀이 되고, 이후에 삭제되지 않기 때문이다. 복구 시에 프로세스의 저장된 상태를 만들기 위해 검사점들이 모두 필요할 수 있으므로 함부로 검사점을 삭제를 할 수 없다. 본 논문에서는 페이지 기반 검사점 도구인 Pickpt를 소개하고, Pickpt가 검사점의 누적 크기 증가 문제를 해결하는 방법을 설명한다. 실험을 통해 기존 점진적 검사점에 비해 Pickpt가 점진적 검사점의 누적 크기를 현저히 줄임을 보였다. Incremental checkpointing, which is intended to minimize checkpointing overhead, saves only the modified pages of a process. However, the cumulative size of incremental checkpoints increases at a steady rate over time because a number of updated values may be saved for the same page. In this paper, we present a comprehensive overview of Pickpt, a page-level incremental checkpointing facility. Pickpt provides space-efficient techniques aiming to minimizing the use of disk space. For our experiments, the results showed that the use of disk space using Pickpt was significantly reduced, compared with existing incremental checkpointing.

삼중구조 시스템의 실시간 태스크 최적 체크포인터 및 분산 고장 탐지 구간 선정

곽성우(Seong Woo Kwak),양정민(Jung-Min Yang) 한국전자통신학회 2023 한국전자통신학회 논문지 Vol.18 No.3

삼중구조 시스템에서는 하나의 프로세서에서 고장이 발생해도 여유도 때문에 주어진 임무를 계속 수행할 수 있다. 본 연구에서는 삼중구조 시스템에 체크포인터 기법을 도입한 후 고장 탐지와 체크포인터를 분리하는 새로운 고장 극복 방법을 제안한다. 먼저 한 개 프로세서에서 고장이 발생하면 고장 탐지와 동시에 모든 프로세서의 상태를 동기화함으로써 고장을 복구한다. 또한 두 개 이상의 프로세서에서 동시에 고장이 발생하면 직전의 체크포인터로 회귀하여 태스크를 재실행함으로써 고장을 복구한다. 본 논문에서는 태스크가 데드라인 이내에서 성공적으로 수행될 확률을 최대화하는 고장 탐지 구간과 체크포인터 구간의 선정 방법을 제안한다. 제안된 방식을 탑재한 삼중구조 시스템을 마코프 체인으로 모델링하고 실시간 태스크의 성공적 수행 확률을 도출하는 모의실험을 수행하여 최적의 해를 구하는 과정을 제시한다. Triple modular redundancy (TMR) systems can continue their mission by virtue of their structural redundancy even if one processor is attacked by faults. In this paper, we propose a new fault tolerance strategy by introducing checkpoints into the TMR system in which data saving and fault detection processes are separated while they corporate together in the conventional checkpoints. Faults in one processor are tolerated by synchronizing the state of three processors upon detecting faults. Simultaneous faults occurring to more than one processor are tolerated by re-executing the task from the latest checkpoint. We propose the checkpoint placement and fault detection strategy to maximize the probability of successful execution of a task within the given deadline. We develop the Markov chain model for the TMR system having the proposed checkpoint strategy, and derive the optimal fault detection and checkpoint interval.

Vehicular datacenter modeling for cloud computing: Considering capacity and leave rate of vehicles

Kim, Taesik,Min, Hong,Jung, Jinman North-Holland 2018 Future generations computer systems Vol.88 No.-

<P><B>Abstract</B></P> <P>In this paper, we propose a vehicular datacenter model in a parking lot, where vehicles can be considered as a resource for cloud computing. One of the crucial issues facing the vehicular datacenter is failures caused by arrival and departure of dynamic resources. These failures result in performance degradation of the execution time because the task must be restarted. In order to reduce execution time and mitigate the effects of uncertainty, we propose a vehicular datacenter model that makes use of a checkpoint mechanism. We first characterize the dynamic vehicles in parking lots considering each vehicle’s capacity and leave rate. We derive the expected execution time to analyze the characteristics of vehicles and propose a resource selection strategy based on that time. We also derive the optimal number of checkpoints for each vehicle that maximizes the efficiency of the checkpoint. We demonstrate the results of our analysis through various evaluations.</P> <P><B>Highlights</B></P> <P> <UL> <LI> We propose a vehicular datacenter model that makes use of a checkpoint mechanism. </LI> <LI> We characterize the vehicles in parking lots considering its capacity and leave rate. </LI> <LI> We propose a resource selection strategy based on the expected execution time. </LI> <LI> We optimize the number of checkpoints that maximizes the efficiency of the checkpoint. </LI> </UL> </P>

5중 구조 실시간 시스템을 위한 최적 체크포인터 구간 선정

곽성우,양정민 대한전기학회 2025 전기학회논문지 Vol.74 No.3

The paper proposes a novel checkpoint management method for a real-time system with a quintuple modular redundancy (QMR) structure wherein multiple fault detections are performed between checkpoints. If the detected faults can be overcome within the context of the QMR structure, they are recovered by simply synchronizing the state values. Otherwise, the system rollbacks to the most recent checkpoint and re-executes the task to recover from the faults. The real-time system having the QMR structure and incorporating the proposed checkpoint scheme is modeled by a Markov chain. Based on the Markov chain model, a probability equation is derived to calculate the likelihood of completing the real-time task within the deadline. The optimal number of checkpoints and fault detections maximizing the probability value are also determined. Numerical experiments are conducted to illustrate the optimization procedure of the real-time system with a QMR structure using the proposed checkpoint management method.

분산 고장 탐지 방식을 이용한 실시간 태스크에서의 최적 체크포인터 구간 선정

곽성우(Seong Woo Kwak),양정민(Jung-Min Yang) 한국지능시스템학회 2016 한국지능시스템학회논문지 Vol.26 No.3

체크포인터를 삽입한 실시간 시스템에서는 고장이 발생하면 고장 직전의 체크포인터로 회귀하여 태스크를 재실행함으로써 과도 고장을 효과적으로 극복할 수 있다. 이번 논문에서는 체크포인터에서 실행되는 데이터 저장과 고장 탐지 과정을 분리한 새로운 체크포인터 방식을 제안한다. 하나의 체크포인터 구간 내에 여러 개의 고장 탐지 과정을 추가하면 고장 발생에서 탐지까지의 지연 시간을 줄일 수 있다. 본 논문에서는 태스크가 데드라인 이내에서 성공적으로 수행될 확률을 최대화하는 고장 탐지 과정의 삽입 방법을 제안한다. 고장 탐지 과정이 분리된 체크포인터 방식을 마코프 체인으로 모델링하고 실시간 태스크의 성공적 수행 확률을 계산하는 모의실험을 수행하여 최적의 해를 구하는 과정을 제시한다. Checkpoint placement is an effective fault tolerance technique against transient faults in which the task is re-executed from the latest checkpoint when a fault is detected. In this paper, we propose a new checkpoint placement strategy separating data saving and fault detection processes that are performed together in conventional checkpoints. Several fault detection processes are performed in one checkpoint interval in order to decrease the latency between the occurrence and detection of faults. We address the placement method of fault detection processes to maximize the probability of successful execution of a task within the given deadline. We develop the Markov chain model for a real-time task having the proposed checkpoints, and derive the optimal fault detection and checkpoint interval.

Cas9-edited immune checkpoint blockade PD-1 DNA polyaptamer hydrogel for cancer immunotherapy

Lee, Jaiwoo,Le, Quoc-Viet,Yang, Geon,Oh, Yu-Kyoung Elsevier 2019 Biomaterials Vol.218 No.-

<P><B>Abstract</B></P> <P>Immune checkpoint inhibitors have been widely studied in immunotherapy. Although antibodies have been more widely used to block immune checkpoints, DNA aptamers have unique advantages for this purpose. Here, we designed a DNA polyaptamer hydrogel that can be precisely cut by Cas9/sgRNA for programmed release of an immune checkpoint-blocking DNA aptamer. As a representative immune checkpoint inhibitor, we used a PD-1 DNA aptamer. Rolling-circle amplification was used to generate a hydrogel comprising DNA with PD-1 aptamer and an sgRNA-targeting sequence. When mixed with Cas9/sgRNA, the PD-1 DNA aptamer hydrogel (PAH) lost its gel property and liberated the PD-1 aptamer sequence. The precise Cas9/sgRNA-mediated release of the PD-1 DNA aptamer, which was confirmed by gel electrophoresis, was found to effectively activate the cytokine-secretion function of splenocytes. In vivo, molecular imaging revealed that PD-1 DNA polyaptamer hydrogel co-injected with Cas9/sgRNA (Cas9/PAH) remained at the injection site longer than free aptamer and yielded significantly higher antitumor effects and survival than hydrogel or free aptamer. Moreover, increased immune cell filtration was observed at tumor tissues treated with Cas9/PAH. These results suggest that our Cas9/sgRNA-edited immune checkpoint-blocking aptamer hydrogel has strong potential for anticancer immunotherapy.</P>