동적계획법을 이용한 제어 핀 최소화를 위한 드롭렛 스케줄 알고리즘
A Droplet Scheduling Algorithm for Control Pin Minimization by Dynamic Programming
- 주제(키워드) 디지털 미세 유체 바이오칩 , 동적 계획법 , 드롭렛 스케줄 , digital microfluidic biochips
- 발행기관 서강대학교 일반대학원
- 지도교수 임종석
- 발행년도 2012
- 학위수여년월 2012. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000047228
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작원 보호를 받습니다.
초록/요약
디지털 미세 유체 바이오칩은 미량의 분석대상물질을 흘려보내면서 바이오칩에 집적되어 있는 각종 생물분자 혹은 센서와 반응하는 양상을 분석할 수 있는 장치이다. 바이오칩에서 제어 핀의 수가 많아지면 입/출력 포트와 제어 핀 사이의 전선 연결이 많아져서 바이오칩의 생산 비용이 증가 한다. 따라서 제어 핀의 수를 줄이는 것은 바이오칩을 합성 할 때 중요한 목적 함수중 하나가 될 수 있다. 제어 핀의 수를 최소화하기 위한 드롭렛 배선을 나타내는 수식에 제어 핀의 수를 직접 목적 함수로 설정 하면 드롭렛 스케줄의 모든 경우를 다 고려해야만 하며 이는 많은 수행 시간을 요구한다. 본 논문에서는 수행시간을 줄이기 위해 직접적으로 제어 핀의 수를 목적 함수로 설정하지 않고 같은 제어 핀을 사용 할 수 없는 셀들의 쌍의 수를 목적 함수로 설정해 동적 계획법을 이용하여 이를 줄이는 드롭렛 스케줄 알고리즘을 제안한다. 제시한 알고리즘은 다기능 바이오칩에서 전체 제어 핀의 수를 줄이기 위한 드롭렛 스케줄에도 적용이 가능하다. 실험 결과 제안한 알고리즘의 제어 핀의 수와 수행시간은 참고문헌 [5]의 결과보다는 증가하였으나 참고문헌[5]를 실제로 작성한 결과보다는 감소하였다. 또한 다기능 바이오칩에 적용했을 때 제어 핀의 수를 고려하지 않고 드롭렛 스케줄을 한 알고리즘의 결과보다 제어 핀의 수가 약 17% 감소하였다.
more초록/요약
Digital microfluidic biochips(DMFBs) is an emerging device that aims to integrate droplet-handling on a chip. Microfluidic processing is performed on the bioassay which are transported, stored, mixed, reacted, or analyzed. For DMFBs, the high pincount demand complicates the electrical connections, thus rendering this kind of chip prohibitively expensive to manufacture. It is important to minimize the number of control pins when fabricating the DMFBs. If the objective function is set to minimize the number of control pins directly, droplet routing to minimize the number of control pins requires a lot of time to perform. In this paper, we propose a droplet scheduling algorithm that minimize the number of pair of incompatible cell in order to reduce the execution time by dynamic programming. In a multifunctional biochip proposed algorithm to reduce the number of control pins can be applied to the schedule for the droplets. Compared with the reference [5], the proposed algorithm reduce the number of control pins. In addition, when applied to multifunctional biochip the result of the proposed algorithm is reduce of approximately 17% the number of control pins than the algorithm without considering the number of control pins.
more