Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
안전 필수 임베디드 제어를 위한 직렬-병렬 작업 그래프의 병렬 실행 극대화(MPE) 문제를 연구합니다. 제안된 LIH 알고리즘은 가중 클리크 분할 문제를 효율적으로 해결하여 최적해에 근접한 결과를 매우 빠른 속도로 도출합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 arXiv Codex (cs.SE)의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기안전 필수 (Safety-critical) 임베디드 제어 프로그램은 각 제어 주기를 제한된 기간 내에 완료해야 합니다. 프로그램의 의존성 구조에 병렬로 실행 가능한 하위 작업들이 포함되어 있을 때, 기존 프로세서에서의 순차적 실행은 병목 현상이 될 수 있습니다. 본 논문은 단계별 배치 (staged batching) 모델 하에서의 직렬-병렬 (series-parallel) 작업 그래프에 대한 최대 병렬 실행 (Maximum Parallel Execution, MPE) 문제를 연구합니다. 이 모델에서 하나의 배치 내의 호환 가능한 작업들은 병렬로 실행되는 반면, 선택된 배치들은 선행 관계를 유지하는 위상 순서 (topological order)에 따라 순차적으로 시작됩니다. 우리는 MPE를 각 배치의 비용이 해당 배치 내에서 가장 느린 작업에 의해 결정되는, 배치 실행 시간의 합을 최소화하는 가중 클리크 분할 (weighted clique-partitioning) 문제로 정식화합니다. 이 문제를 효율적으로 해결하기 위해, 우리는 라그랑주 기반 반복 휴리스틱 (Lagrangian-based Iterative Heuristic, LIH)을 제안합니다. LIH는 단일 열 (singleton columns)과 무작위 탐욕적 클리크 생성 (random greedy clique generation)을 통해 가격 책정 필터링이 적용된 실행 가능한 후보 배치들의 제한된 풀을 구축합니다. 그런 다음, 열 선택을 안내하기 위해 라그랑주 가격 책정 (Lagrangian pricing)을 적용하고, 합법적인 클리크 분할을 복구하기 위해 복구 절차 (repair procedure)를 사용합니다. 가중 혼합 그래프 채색 (weighted mixed-graph-coloring) 분기 한정법 (branch-and-bound) 베이스라인 및 무작위 탐욕적 (randomized greedy) 베이스라인과의 실험 결과, LIH는 유사한 인스턴스의 91.25%에서 정확한 최적해와 일치하였으며, 평균 격차(gap)는 0.073%, 평균 실행 시간은 18.19 ms였습니다. 가장 큰 정확한 참조 노드 설정에서 정확한 베이스라인은 평균 수백 초가 소요되는 반면, LIH는 50 ms 미만을 유지합니다. 나아가 우리는 PLCOpen 스타일의 프로그램을 MPE 그래프로 변환하고, LIH로 최적화하며, FPGA 지향 HDL로 번역한 뒤, 원래의 PLC 스캔 실행과 비교 시뮬레이션하는 엔드-투-엔드 PLC 래더 로직 (ladder-logic) 사례 연구를 제시합니다.