고성능 멀티프로세서를 위한 유전 알고리즘 기반의 반복 데이터흐름 최적화 스케줄링 방법 :An iterative data-flow optimal scheduling method on genetic algorithm for high-performance multiprocessor

장정욱

추천

검색

자료유형: 학위논문

저자정보: 장정욱 (세명대학교, 세명대학교 대학원)

지도교수: 인치호

발행연도: 2016

저작권: 세명대학교 논문은 저작권에 의해 보호받습니다.

이용수1

이 논문의 연구 히스토리 (2)

2016

고성능 멀티프로세서를 위한 유전 알고리즘 기반의 반복 데이터흐름 최적화 스케줄링 방법

장정욱 전산정보학과 2016.01 학위논문

2015

고성능 멀티프로세서를 위한 유전 알고리즘 기반의 반복 데이터흐름 최적화 스케줄링 알고리즘

장정욱 , 인치호 한국인터넷방송통신학회 논문지 2015.01 학술저널

이 논문의 후속연구가 궁금하신가요?
연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
이 논문의 연구 히스토리 확인하기

초록· 키워드

오류제보하기

본 논문에서는 멀티프로세서 아키텍처 상에 반복적인 데이터흐름 알고리즘을 스케줄링하는 방법을 제안한다. 기본적인 하드웨어 모델을 기반으로 멀티프로세서 아키텍처라는 세부적인 특성을 가지도록 확장하여 용량이 제한된 통신 네트워크상에 전송할 데이터를 라우팅하는데 필요한 하드웨어 모델을 구현하고, 스케줄링 방법을 적용한다.
제안한 스케줄링 방법은 세 가지 계층으로 구성된다. 가장 상위 계층에 구현된 유전 알고리즘은 반복 데이터흐름 그래프의 최적화를 담당한다. 유전 알고리즘은 대상이 되는 연산들에 대하여 서로 다른 조합을 생성한다. 그리고서 이 조합들은 중간 계층으로 전달된다. 이 중간 계층에는 전역 스케줄링이 위치하며, 연산들의 조합을 바탕으로 스케줄링에 관한 주요 결정을 이 스케줄이 내리게 된다. 마지막으로, 하부 계층에서는 하드웨어 세부사항을 고려하며 블랙-박스 스케줄링을 이용한다. 연산에 대한 스케줄링을 완료하고, 세부적인 하드웨어 모델이 이 결정을 준수하는지 확인한다. 스케줄 사이에 사이클을 삽입할 수 있는 두 가지 스케줄링을 통해 유효한 스케줄을 항상 빨리 찾아낼 수 있다.
본 논문에서 제안한 스케줄링 방법의 성능을 테스트하기 위하여 다섯 가지 필터들에 대한 벤치마크를 수행한다. 통신지연과 제한된 용량을 갖는 통신 네트워크를 포함한 하드웨어 모델을 통해 얻어진 런타임의 증감값을 비교하여 합당한 시간 안에 양질의 스케줄을 찾아낼 수 있음을 입증한다.

목 차 ⅰ
그림 목차 ⅳ
표 목차 ⅵ
요 약 ⅶ
제 1 장 서 론 1
제 2 장 반복 알고리즘의 스케줄링 문제 5
2.1 스케줄링의 이론 5
2.1.1 데이터흐름 그래프 6
2.1.2 스케줄링에 관한 기본 개념 8
2.1.3 성능 경계 12
2.2 관련 스케줄링 방법 15
2.2.1 반복 알고리즘과 비반복 알고리즘 16
2.2.2 반복 알고리즘을 위한 스케줄링 방법 17
2.2.3 무시할 수 없는 통신지연 18
2.2.4 (비)선형 정수 문제의 구성 19
2.2.5 유전 알고리즘 20
2.2.6 통신지연과 DSP 아키텍처 22
2.3 멀티프로세서 23
2.3.1 가용한 멀티프로세서 24
2.3.2 현실적 하드웨어 모델 26
2.3.2 정리 27
2.4 스케줄링의 문제점 27
제 3 장 반복 데이터흐름 스케줄링 방법 30
3.1 스케줄링 개요 30
3.2 스케줄링 목적 32
3.3 전역 스케줄링 알고리즘 33
3.4 블랙-박스 스케줄링 알고리즘 34
제 4 장 유전 알고리즘 기반의 스케줄링 알고리즘 36
4.1 전역 스케줄링 알고리즘 36
4.1.1 스케줄링 방법 제안 36
4.1.1.1 시간의 표현 37
4.1.1.2 선행 관계 40
4.1.1.3 스케줄링 인스턴트 46
4.1.1.4 신규 사이클의 삽입 48
4.1.2 스케줄링 알고리즘 50
4.1.3 스케줄링 제안점 52
4.1.3.1 연산 선정 52
4.1.3.2 유효 시작시간의 범위 52
4.1.3.3 유효한 스케줄 인스턴트 탐색 53
4.1.3.4 선호 시작시간 54
4.1.3.5 삽입 사이클 결정 57
4.1.4 스케줄링 알고리즘의 수행 흐름 60
4.2 블랙-박스 스케줄링 알고리즘 67
4.2.1 전역 스케줄링 알고리즘에 대한 수정사항 68
4.2.2 하드웨어 모델 69
4.2.3 블랙-박스 스케줄링 알고리즘 69
4.2.4 스케줄링 제안점 71
4.2.4.1 스케줄링 방향 72
4.2.4.2 FU 넘버링 72
4.2.4.3 전역 스케줄링과의 유사성 74
4.2.5 블랙-박스 스케줄링 알고리즘의 수행 흐름 74
4.2.6 블랙-박스 스케줄링 알고리즘 결과 79
4.3 유전 알고리즘 85
4.3.1 유전 알고리즘의 기본 원리 85
4.3.1.1 유기체 85
4.3.1.2 진화 87
4.3.2 구현 세부사항 91
제 5 장 스케줄링 알고리즘의 튜닝 94
5.1 성공확률 94
5.2 전역 스케줄링 튜닝 97
5.2.1 반복주기의 초기값 98
5.2.2 연산의 선택 101
5.2.3 선호 시작시간 103
5.3 블랙-박스 스케줄링 튜닝 105
5.3.1 스케줄링 방향 105
5.3.2 FU 넘버링 108
5.4 유전 알고리즘 튜닝 108
5.4.1 크로스오버 연산자 109
5.4.2 돌연변이 연산자 112
5.4.3 적합도 함수 114
제 6 장 실험결과 117
6.1 벤치마크 환경 117
6.2 무시할 수 있는 통신지연 122
6.3 블랙-박스 통신 모델 125
제 7 장 결론 131
참고문헌 133
기호설명 139
Abstract 140
연구 실적 목록 142
감사의 글

최근 본 자료

전체보기

구분	그룹	데이터 항목
AI 학습용 데이터	원문	원문 PDF 파일
AI 학습용 데이터	원문 + 메타 (기본/상세)	원문 PDF 파일 및 서지정보 CSV
대량 구매용 데이터	B2B 구독 방식	특정 자료 한정으로 원문 접근 권한 부여
대량 구매용 데이터	URL 전달 방식	바로 PDF 뷰어를 열람할 수 있는 URL 제공

구분	그룹	데이터 항목
AI 학습용 데이터	기본 메타	발행기관명, 간행물명, 권호명, 권(vol), 호(issue), 통권, 발행연도, 발행월, 논문명, 저자명, 시작페이지, 종료페이지, 전체페이지, 상세페이지URL
상세 메타 데이터	발행기관 메타	발행기관 이명, 영문명, 창립연도, 홈페이지URL, 발행기관 소개
	간행물 메타	부제목, 간행물 유형, ISSN, ISBN, 최초발행연도, 폐간연도, 간행빈도, 발행주기, 등재사항, 이용수, 피인용수, 권호수, 논문수, 표지이미지
	논문 메타	작성 언어, 부제목, 대등제목, 목차, 키워드, 초록, 이미지, 참고문헌, 이용수, 피인용수, 논문활용도, DBpia통합주제분류, KDC분류, DDC분류, 한국연구재단분류, UCI, DOI
	저자 메타	소속기관, 소속부서, 직급, 연구분야, 연구키워드, 이용수, 피인용수, 저자 논문활용도

구분	그룹	데이터 항목
※ 결합형/맞춤형 메타 데이터는 신청 내용에 따라 다양하게 제공 가능
이용순위 정보	주제분야별 많이 이용된 논문	“인문학”에서 많이 이용된 논문 TOP100
	이용기관별 많이 이용된 논문	“중고등학교”에서 많이 이용된 논문 TOP100
	세부기관별 많이 이용된 논문	“서울대학교”에서 많이 이용된 논문 TOP100
	키워드별 많이 이용된 논문	“Chat GPT”에서 많이 이용된 논문 TOP100
키워드 정보	많이 이용된 키워드	특정기간/분야/저널 내 많이 이용된 키워드
	많이 발행된 키워드	특정기간/분야/저널 내 많이 발행된 키워드
	많이 검색된 키워드	특정기간/분야/저널 내 많이 검색된 키워드
	연구 트렌드 키워드	특정 키워드 연관 연구동향 분석 데이터 키워드

논문 기본 정보

이 논문의 연구 히스토리 (2)

초록· 키워드

목차

최근 본 자료

댓글(0)