$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

최소의 스케줄 길이를 유지하는 결함 허용 태스크 스케줄링 알고리즘
A Fault-tolerant Task Scheduling Algorithm Supporting the Minimum Schedule Length 원문보기

정보처리논문지 = The transactions of the Korea Information Processing Society, v.7 no.4, 2000년, pp.1201 - 1210  

민병준 (인천대학교 컴퓨터공학과)

Abstract ▼ AI-Helper 아이콘AI-Helper

In order to tolerate faults which may occur during the execution of distributed tasks in high-performance parallel computer systems, tasks are duplicated on different processors. In this paper, by utilizing the task duplication based scheduling algorithm, a new task scheduling algorithm which duplic...

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 본 논문에서 다룰 문제는 주어진 테스크 그레프에내해서 최소의 스케줌 길이를 유지하면서 그래프 내의모뜬 테스■크들이 서로 다른 두게 이상의 프로세서에 중복 할담되도록 하는 것이다. 이와 동시에 모든 태스크 중복 할당하弋데 요구되는 프로세서의 개수를 최대한 줄일 수 있는 방법을 찾는 깃이다.
  • 본 논문에서는 대스크 중복을 기반으로 하는 알고기즘을 미용하며 모든 티스크들이 서로 다른 두개 이상의 프로세서에 중복 할당되도록 하여 길함허용 기법을수묨하도록 히먼서 최소수행시간믈 갖는 알고리즘음제시헌. 다.
  • 也7]에서는 태스크 중복을 기반으로 최저의 스케줄 길이를 갖는 알고리즘(task duplication based scheduling)을 제시하였다. 이 알고리즘은 태스크들 간의 통신비욤을 고려하여 비용이 많이 드는 태스크를 이와 연결된 태스크가 할당된 동일한 프로세서에서 할당하면 스키줄 길이를 최소화 할 수 있다는 개념에 바탕을 둔 것이다. 여기서는 중복이 반드시 필요한 경우에만 하도록 하고 있으벼, 간단한 조전을 만족하면 최적의 수행시간을 제공하는 것으로 증멍되었다.

가설 설정

  • start time of t)를 구하게 된다. 태스크 G의 succ증 하나인 태스크 ti( 가 있고 데스크 G가 해스m tk의 fpred라먼 누 태스크는 같은 프로세서에 할당될 수 있으므로 그것을 가정하여 let化)는 1아(圮로 하고 二L렇지 않으면 두 태스크 사이의 통신비욤을 고려하여정힌. 디.
본문요약 정보가 도움이 되었나요?

참고문헌 (14)

  1. T. Adam, et. al. 'A Comparison of List Schedules for Parallel Processing Systems,' Comm. ACM. Vol.17, No.l2, pp.685-690, Dec., 1974 

    상세보기 crossref

  2. I. Ahmad and Y.K. Kwok, 'On Exploiting Task Duplication in Parallel Program Scheduling,' IEEE Trans on Parallel and Distributed Systems, Vol 9, No9. pp 872-891. Sept. 1998 

    상세보기 crossref

  3. I.Ahmad and Y.K. Kwok, 'On Parallelizing the Multiprocessor Scheduling Problem,' IEEE Trans. on Parallel and Distributed Systems, Vol 10, No 4, pp.414-432, Apr. 1999 

    상세보기 crossref

  4. A. Bertossi, et al, 'Fault-tolerant Rate-monotonic First- fit Scheduling in Hard-real-time Systems.' IEEE Trans. on Parallel and Distributed Systems, Vol10, No 9, PP.934-945, Sept. 1999 

    상세보기 crossref

  5. H. Chen. et al., 'Static Scheduling Using Linear Clustering Task Duplication,' Proc Int'l Conf Parallel and Distributed Computing and Systems, pp.285-290, Oct 1993 

  6. S Darbha and P. Agrawal, 'A Task Duplication based Scalable Scheduling Algorithm for Distributed Memory Systems,' J. of Parallel and Distributed Computing, Vol.46, pp,15-27, 1997 

    상세보기 crossref

  7. S. Darbha and P. Agrawal. 'Optimal Scheduling ？Algonthm for Distributed-Memory Machines,' IEEE Trans, on Parallel and Distributed Systems, Vol.9, No,1, pp.87-95, Jan 1998 

    상세보기 crossref

  8. R. Graham et, al , 'Optimization and Approximation in Determmstic Sequencing and Scheduling: A Survey.' Annals of Discrete Mathematics, pp,287-326, 1979 

  9. C Hou and K,G. Shin,'Module Allocation with Timing and Precedence Constraints in Distributed Real-time Systems,' IEEE Proc. Real Time Systems Symp. pp.146-155, Dec 1994 

  10. K.H. Kim, et al., 'Fault-tolorat Execution of Real time Tasks through Duplex Assignment within Parallel Computers.' Proc, Int'l Conf. Parallel and Distributed System. Dec 1992 

  11. K.H. Kim and B.J. Min, 'Approaches to Implementation of Multiple DRB Stations in Tightly Coupled Computer Networks,' Proc Int'l Computer Software and Applications Conf , Sept 1991 

  12. P. Mahcshwari and H. Shen, 'An Efficient Clustering Algorithm for Partitioning Parallel Programs,' Parallel Computing Vol.24, pp,893-909, 1998 

    상세보기 crossref

  13. G. Manimaran and C. Murthy, 'A Fault-tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-time Systems and its Analysis,' IEEE Trans on Parallel and Distributed Systems, Vol.9, No 11, pp,1137 -1152, Nov. 1998 

    상세보기 crossref

  14. T. Varvarigou and J. Trotter. 'Module Replication for Fault-tolerant Real-time Drstributed Systems,' IEEE Trans, on Rehability. Vol.47, No.1, pp.8-18. Mar 1998 

저자의 다른 논문 :

관련 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로