EdgeProg: Edge-centric Programming for IoT Applications

2021 / 4 / 29 iMES 세미나

Abstract

IoT 앱 개발 : device side + server side에서의 분리된 프로그래밍 포함
- simple한 app에서는 충분한 방법
- 복잡한 app에서는 적절하지 않다 ( 복잡한 interaction / 집중적인 data processing )
Edgeprog 제안 ( edge 중심적 프로그래밍 접근법 )
- user : 중앙집중식으로 app logic을 쓸 수 있음
  - augmented if-this-then-that ( IFTTT ) syntax
  - 가상 센서 매커니즘
- 프로그램은 edge server에서 처리될 수 있음 ( 최적의 latency 달성 )
  - 실제 app code 자동으로 생성
  - device code와 server code를 지능적으로 분할
- 동적 linking / loading 사용
  - start에서 app별 code를 실행하지 않는 다양한 IoT device에 device code를 배포
- 결과 ( 최신 접근법과의 비교 )
  - 20.96%의 실행 latency 감소
  - 79.41%의 code line 감소

Introduction

IoT 앱개발 : device측 + server측의 분리된 프로그래밍
- Ex) device 측에는 센서, server측에 분석을 위한 data를 전달하는 등
- 간단한 app 개발에는 효율적 / 복잡한 app 개발에는 적절하지 않음

Complex interactions

Ex) 문이 열릴 경우 센서가 감지하여 LED를 켜려고 함
기존 프로그래밍 스타일 : app logic이 다른 센서 node로 분산
- 시스템의 복잡성 증가 / 관리성 저하

Intensive data processing

Ex) speech 인식 app 개발
방법
- 모든 센서 data를 복잡한 인식 알고리즘을 돌리는 server로 전송
  - 과도한 에너지 소비 ( 많은 양의 trasmission )
- IoT device에서 인식 알고리즘 수행
  - 과도한 delay 유발 ( 연산 파워의 부족 )
separate programming : 적절한 프로그래밍 방법을 선택해야함

엣지컴퓨팅의 인기 증가에 따라 다른 프로그래밍 접근법을 제안
- 다수의 IoT node : sensing / actuation ( 실행 ) 수행
- 각각 local edge로 연결됨 ( 복잡한 연산 수행 )
- edge server : power suffly 존재 / energy 제약사항이 적음
- edge computing : 적은 processing delay / 더 좋은 privacy 제공
- EdgeProg : 새로운 프로그래밍 스타일 / 시스템 구조
  - IoT app 프로그래밍을 크게 단순화
  - 전체 시스템의 효율 손실 없이 다양한 app에 대해 재프로그래밍될 수 있는 일반적인 IoT system
  - 개발자 : high-level 언어 사용
    - 전체 app logic + IoT app 통합
  - 프로그램이 edge server에서 처리될 수 있음
    - 실제 app code를 생성
    - device code / server code로 분할
  - edge-centric 접근법 : 프로그램이 edge에서 실행되어지는 듯한 효과
  - 일반적인 IoT node : 처음부터 app별 code를 실행하지 않음
    - app의 첫 실행에 IoT node의 메모리에 app별 code가 자동 load될 것
- Challenge
  - 다중 device 상호작용 + data 집중적 연산을 지원하는 edge-centric 언어 설계 방법?
  - user-인식 프로그램을 분할하여 최적의 delay를 달성하는 방법?
  - 이기종 sensor node가 device측 code를 동적으로 load하고, 효율적으로 실행할 수 있도록 하는 매커니즘 설계 방법?
- 일관성 있는 언어 설계
  - 목적
    - edge 중심 프로그래밍 지원
    - app 개발 프로세스 속도 향상
  - 다중 device 상호작용 지정
  - IFTTT 기반 언어 기반 / 확장
    - 목적
      - 표현력 높임
      - data 집약적 연산 채택
    - 가상 센서 사용
      - 머신러닝으로 자신들의 data 처리 로직 설계를 가속화
EdgeProg : 자동 코드 분할 수행
- 각 device의 연산 능력을 완전히 활용
- 최적의 latency 달성
- user가 작성한 프로그램 -> data flow 그래프로 추출
- partitioning 문제 -> integer programming 문제로 공식화
- 최적의 partition을 얻기 위해 lp_solve 해결자 사용
Contiki OS에서 구현
- 플랫폼 교차지원
- 동적 linking / loading 기술 사용 -> 런타임에 최적화된 실행파일 load 능력 구현
- app 실행 중 app의 logic을 바꾸는 대안
  - 가상머신 이용
  - 스크립팅 언어 사용
- 대안을 사용하지는 않을 예정 ( 동적 linking / loading에 비해 overhead가 상당 )
구현 평가
- EdgeProg 언어 : 다양한 IoT app logic을 표현할 수 있음
  - code line을 79.41% 줄일 수 있음
- 최신 partitioning 시스템과의 비교
  - 평균 20.96% / 최대 99.05% 감소
- 동적 linking / loading 기술 사용과 대안책을 사용할 때의 비교
  - 가상머신을 사용하는 경우 : 9.98X
  - 스크립팅 언어를 사용하는 경우 : 6.37X
- 프로파일링 메소드 정확도 평가
  - 85%+의 정확도
contribution 요약
- EdgeProg ( IoT app을 위한 edge 중심적 프로그래밍 시스템 ) 제안
  - 흩어진 app logic -> 사용하기 쉬운 방법으로 logic을 표현할 수 있도록 함
- task의 makespan을 최소화하기 위해 code 분할 문제를 공식화
  - 분할 알고리즘 : 각 stage의 배치 최적화 ( 프로세싱 / 네트워크 latency를 모두 고려 )
- EdgeProg 개발 / 평가 ( 실제 app / 벤치마크 )
  - 최신 연구들과 비교하여 latency 감소 / line 감소

Background and EdgeProg Usage

A. Background

Dynamic linking and loading of IoT devices

IoT device의 over-the-air reprogramming 기술 중 하나 ( 과잉 재프로그래밍 )
- linking phase
  - on-device reprogrammer : 파일의 구조화된 정보 -> 실행 가능하고 link 가능한 파일 ( ELF ) / 그것들의 변형 ( CELF / SELF ) 로 파싱
  - ELF 파일의 data / text segment에 대해 ROM / RAM 등을 할당
  - 재배치 수행 ( symbol table에서 발견되거나 ELF에서 재배치 정보를 사용하여 계산된 symbol의 실제 메모리 주소로 data 및 text segment를 패치 )
- loading phase
  - text segment를 할당된 ROM에 write
  - data segment를 RAM에 복사
  - binary가 load되어짐 / 실행 준비 완료
대안들 ( 가상머신 / 부트로더 ) 와 비교하여 장점이 있음
- 높은 장기간 효율성 ( 가상머신 code 대신 고유 code를 실행하기 때문 )
- 재부팅이 없는 update ( 에너지 효율 )

Virtual sensor

다른 장소에 위치할 수 있는 실제 센서들로부터 감지한 데이터를 추상화하는 논리적 실체
전통적인 하드웨어 센서 : 물리적 특성의 raw 측정값만을 제공함
- 수익성이 없음 ( 높은 level의 domain 의존 정보로 변환해야만 수익성이 생김 )
- 값진 data를 얻기 위해서는 여러 sensor들의 조정이 필요함 ( 온도 / 연기 센서로 화재위험 감지 )
위의 한계점과 센서 data 처리를 유연하게 하기 위해 고안되어짐
여러 하드웨어 센서에서 감지된 data + 데이터 처리 알고리즘의 결합으로 일반적으로 물리적으로 측정할 수 없는 간접 측정 / 이벤트 제공
EdgeProg : 기본 IFTTT 문법의 확장형 -> 집중적인 data 처리를 하기 위한 사용하기 쉽고 표현적인 처리 제공

B. EdgeProg Usage

Ex) SmartHomeEnv
- 2개의 센서 ( 온도 / 습도 ) data를 입력으로 받음
- 에어컨 / 제습기를 켤 수 있음 ( 2개의 input이 threshold를 넘길 경우 )
- 2개의 센서 : edge server와 무선 연결 ( 라즈베리 파이 등 )
- 전통적인 관점 : edge server에 주기적으로 센서값 전송하는 기능이 있는 app별 code로 미리 설치
  - edge : reading값을 처리 / 미리 정의된 인터페이스 사용 -> 센서와 상호작용
- EdgeProg 사용 : app별 logic 없이 “idle” 프로그램으로 미리 설치
  - 모든 app logic : 향상된 IFTTT 기반 언어로 구현
  - edge 서버에서 해석 / 처리되어짐
- 예시
```
Application SmartHomeEnv {
    Configuration { // device와 그들의 interface 선언
        TelosB A(TEMPERATURE);
        TelosB B(HUMIDITY);
        Edge E(turnOnAC, turnOnDryer);
    }
    Rule { // IFTTT를 따른 app별 login
        IF (A.TEMPERATURE > 30 && B.HUMIDITY > 70)
            THEN (E.turnOnAC && E.turnOnDryer)
    }
}
```
  - edge 서버 : code를 자동으로 2개로 분할
    - device측 component / edge측 component
    - device측 컴포넌트 : load 가능한 모듈로 컴파일 -> 센서 node로 전송
    - 한번 notice하면, “idle” 프로그램이 실행을 위해 app별 모듈을 동적으로 load할 수 있음
핵심
- 전체 app code를 자동으로 분할할 수 있음 -> 실행성능 최적화
  - 전산집약적 IoT 작업에 필수적 ( 음성인식 / 영상감시 등 )
  - device에 code를 배치하는 것보다 작업에서 더 나은 성능을 보이는 경우, edge 측으로 code를 분할

EdgeProg Overview

A. Design Goals

Edge centric

개발 중에 app logic을 조각으로 분해할 필요가 없도록 edge-centric한 접근법 제공

Latency-aware

edge device에 조정된 app에게 적시성은 치명적인 성능 문제와 직결
EdgeProg : 주어진 input에 대한 시간최적 solution을 제공하는 능력이 필요

Automatic

EdgeProg : user의 idea를 표현하는데 아무런 이득이 없는 세부사항을 구상 / app 개발을 단순화하고 가속화하기 위해 인간을 loop에서 제거한다는 것을 의미

B. EdgeProg Architecture

user : edge-centric한 app code를 바로 작성할 수 있음
- 분산된 프로그래밍 스타일 / 각 stage에서 물리적 placement 등을 고려하지 않아도 됨
system : user code를 input으로 받음
- 전처리, feed -> code partitioner로 전달
code partitioner : 각 device의 time profile + 파티셔닝 알고리즘에 의해 각 stage에서의 최적의 파티션 / placement를 탐색
code generator : user가 작성한 code 전처리 -> 컴파일이 가능한 code로 변환
- code compiler : 실행 가능 / load 가능한 binary로 변환
실행파일 : 공중을 통해서 배포 / edge device에 배치

User Input

EdgeProg 프로그래밍 모델에 의해 작성되어짐
- interface에 의해 지정된 device에서 제공하는 actuator
- implementation에 의해 지정된 가상 센서의 출력
- 위를 이용하여 app logic을 지정하는 rule 개념 중심으로

Code Partitioner

user input app에 대한 최적의 파티션 제공

Time profiler

각 스테이지의 시간 정보 : code partitioner의 중요한 input
profiling phase : 다른 플랫폼에서의 실행 시간 얻음
low-end 센서 node : cycle-accurate 시뮬레이터 사용
- MSPsim ( MSP430 기반 node ( TelosB ) )
- Avrora ( AVR 기반 node ( MicaZ ) )
- timing 정보를 얻기 위함
high-end 센서 node : low-end보다 정확도가 낮음
- 원인 : 자동 frequency scaling 전략 사용 -> 시뮬레이터의 정확도 감소
real device에서 raw timing data를 모으는 것은 좋지 않음, 실현 불가능함
- edge server의 하드웨어 interface의 한계
- high-end device를 profiling하기 위해 gem5이라는 cycle-accurate 시뮬레이서 근접 방법 채택

Network Profiler

네트워크 상태 : 파티션에 공급되는 주요 metric
- deploy되었을 때 network 상태 파악 방법 : M-SVR 알고리즘 사용
  - Multiple-output support vector regression : 간격 시퀀스에서의 미래 네트워크 상태를 나타내는 예측 시퀀스를 생성
  - loading agent에서 0.1Hz로 샘플링된 대역폭 / RSSI 등이 fed되어짐
  - predictor : 미래 throughput / 패킷당 전송시간 추정치 출력 ( 추가 세분화 시간 계산 목적 )
- 예측 알고리즘 : 시스템의 블랙박스 역할
  - 다른 예측 알고리즘 사용해도 괜찮음

Code Generator

생성된 최선의 파티션 : code generator에서 진행되어짐
high-level의 EdgeProg 언어 -> 컴파일 가능한 C code로 변환

Code Compiler

받은 code -> 실행가능 파일로 변환 ( target flatform에 맞춰서 )
이후 배포 시작
현재 4개의 플랫폼 / 4개의 MCU 구조 지원 ( ATMega, MSP, ARM, x86 )

Loading Agent

시스템 초기 : loading agent를 제외하고 node에서 실행되는 app별 logic이 없음
edge와 주기적 통신 : 새로 load 가능한 app을 위함
app이 컴파일 이후 배포되기 시작할 때, 목적지에 있는 loading agent : 실행 가능 감지 / 검증 / 수신
- 이후 동적으로 실행

System Design

A. EdgeProg Programming Language

EdgeProg : DSL 언어 수용 ( 개발자들이 app 개발할 때 사용하는 언어 )
- 흩어진 프로그래밍 스타일의 문제점 해소 / app 개발 프로세스 가속 목적
- Rule-based Domain-Specific Language
- app : 3개의 파트로 구성되어짐
  - configuration / implementation / rule

Edge-centric programming model

edgeprog : edge 중심 설계 목표
- implementation의 세부사항보다 global behavior에 user를 집중시켜야함
- 개발자 : Rule 키워드 활용 -> 전체 app logic을 중심으로 app 구성 가능
여러 DSL이 있음 : sensornet 연구에서 개발자가 macro-programming model에 집중할 수 있음
- 최근에는 기존 연구가 좋지 않음 ( app 이동성, 작동 부족 등에 대한 제약조건 )
IFTTT 프로그래밍 기법 : 다른 연구들에 비해 단순 / 효율적 ( hight-level app logic을 표현할 때 )
- 첨단 산업 솔루션으로 활용 중
- edgeprog에서도 비슷한 문법 활용 : 통일되고 명시적인 방식으로 자신의 아이디어 표현 가능
- Configuration, Implementation 추가 : Rule 파트에서 사용될 구성요소의 세부 정의 / 사양 등 표현

Full support of virtual sensor

요즘의 방대한 data 처리를 수용하기 위해 DSL를 가상 센서를 이용하여 강화
- 가상 센서 : 복잡한 data 처리 알고리즘을 표현하는 효율적인 접근법
  - feature 추출 / 분류 2가지 단계로 구성
가상 센서 VoiceRecog
- A.MIC 인터페이스 : 입력 음성 단편 생성
- 가상 센서 : 입력된 음성이 “open”인지 아닌지 인식
- FE / ID 두 단계로 구성된 pipeline
  - 각 stage마다 setModel() 존재 ( 음성인식 지원 )
- 17개의 data 처리 알고리즘 ( 12개의 추출 / 5개의 분류 )
- FE / ID : 일반적인 pipeline 구성
  - 2개 이상의 여러 stage / 병렬 stage도 지원함
green 개발자 : 어떤 센서가 어떤 예상 출력과 어떤 관련이 있는지 모름 -> 복잡성이 높음
- 완화 방법 : inference-agnostic 가상 센서
  - 관련 센서 set와 가상 센서 예상 출력 제공
edgeprog : 처음에 샘플 app을 생성
- 개발자 : 충분한 training data를 얻기 위해 원하는 event를 기록해야함
- edgeprog : 입력 센서 <-> 기록된 event 간의 관계를 반영하는 모델 훈련
- 이후 다른 가상 센서와 비슷하게 분할 / 보급

Explicit data flow

약 45%의 code line이 data flow 구축 / 상호작용을 위해 작성되어짐
- 상당한 양 / 프로젝트의 복잡성 증가 원인
여러 device 상호작용 : 네트워크 패킷 구성에서 생기는 data flow를 더 복잡하게 함
일반적인 IoT app에서의 data flow : 센서 data로부터 생성 / 시작 ( 여러 알고리즘으로부터 생성 )
- database에 저장되거나, 실행 IoT 노드로 command-back
- So, 이 3 단계에 data flow를 명시적으로 제작
개발자 : data 및 사용 가능한 action을 인터페이스로 지정
- 사용 가능한 인터페이스 : 공급업체 / prototype 개발자에 의해 결정되어짐
데이터 처리 목적 -> 가상 센서, rule : 인터페이스 직접 사용 / 호출 -> 통일적이고 명시적인 data flow 초래

B. Code Partitioning

code 분할 subsystem 목적 : 적절한 stage로의 user input 분리 / 각 stage마다 최선의 placement 얻기
- 사용자 input app -> 연산 stage를 나타내는 logic block으로의 전처리
- rule의 data flow 그래프 생성 ( app logic, stage 의존도 파악 목적 )
- latency-ware : edgeprog의 설계 목적 중 하나
  - latency 최소화 문제 공식화 / 각 stage의 최적 배치를 찾는 solver 사용
파티셔닝 알고리즘 핵심 : 연산을 data source와 가깝게 밀어넣음 / 각 device의 연산능력을 최대한 사용하여 latency 감소 달성
- edgeprog : 좋은 연산-전송 tradeoff를 달성하는 최적의 placement 찾을 수 있음

Logic blocks and data flow graph construction

더 이상의 구현 / 최적화가 불가능한 2가지 차이가 있음 ( 이 프로그래밍 언어의 compact한 특성 )
- 일부 stage : 암시적으로 정의되고, app에서 사용될 수 있음
  - rule stage에서 필요하지만, 그것이 app에서 구상되어지는 경우가 있음
- 토플로지 정보 : 전체 최적화에 필요 ( 그런데 이것도 app에서 암시되어짐 )
차이 해소 방법 : node가 logic block으로 표시되는 app의 data flow graph를 구성
- logic block : app의 독립적인 building block
  - code 생성을 위한 input source 포함해야함
  - 배치 / 알고리즘 / 시간 profiling에 필요한 파라미터 등의 정보 포함해야함
  - tuple <functionality, placement>로 정의되어짐
- functionality
  - SAMPLE, ACTUATE, CONJ 의 tenet에서의 tasklet primitive 차용 ( 광범위한 data 수집 / 처리 작업을 위한 building block )
  - 가상 센서 배치를 수용하기 위한 알고리즘 primitive 추가 ( GMM )
  - logic block의 data 소스 : primitive의 첫번째 argument로 선언되어짐
- placement
  - 2종류의 code block : pinned / movable
    - pinned : 물리적으로 구속된 기능
      - SAMPLE : device에 배치되어야만 함
    - placement : 고정된 block에 고정되어짐
      - logic block에서 해당 device 별칭 사용
    - movable : 불확실성을 표기하기 위해 ? 같이 표시
      - device / edge에 잠재적으로 배치됨
명시적으로 선언된 logic block 제외하고 일부 block : 완전그래프에서도 필요 / 사용자 app에서 암시적으로 그려짐
- 내재된 block으로 data flow graph 완성하기 위해서는, Rule에서 정의된 모든 규칙을 아래와 같은 전략으로 분석
  - IF-statement에서 가상 센서를 활용하는 조건에서, Implementation 부분 참조하여 stage pipeline 확보 / SAMPLE 블록 삽입
  - 센서 값만을 비교하는 조건에서는, 2개의 stage로 변환 ( SAMPLE, CMP )
  - CONJ 블록 : IF-statement에서 모든 conjunction 표기
  - Then-statement에서의 각 action : 2개의 block으로 변환
    - AUX : 보조 movable 블록 ( statement가 edge / local에서 실행될 것임을 나타냄 )
    - ACTUATE : 고정 블록 ( action을 나타냄 )
- data flow graph : 유향 비순환 그래프로 나타내어질 것
  - 정점 : logic block
  - 간선 : data flow가 있음을 나타냄

The ILP problem for optimal partitioning

data flow graph의 존재 : 최선의 파티셔닝 문제 -> 수치 최적화 문제로 공식화 가능
- 최선의 파티셔닝 결과 : logic block을 각각 가장 선호되는 연산 device에 할당하는 것
- 할당 결과 : 이진값 $X_{b_is_i}$로 표기 ( 1이면 할당 / 0이면 비할당 )
이전에 있던 파티셔닝 알고리즘을 가져와서 사용 ( Wishbone )
- 2가지 차이점에 의해 이곳에서 실현될 수 없음
  - Node weight
    - 그래프에서 해당 logic block의 처리 시간을 나타내는 vertax에 weight 할당할 때의 문제
    - movable block의 가중치 : local / edge 서버 처리시간의 2배
      - wishbone graph에서의 vertax 가중치 : 1개의 weight
  - Optimization goal
    - wishbone에서의 최적화 목표 : 연산 budget / 네트워크 bandwidth 최소화
    - edgeprog에서의 최적화 목표 : latency에 초점
    - 서로 원하는 최적화가 달라 공식이 적합하지 않음
- edgeprog의 목적 : task 실행 latency 최소화 ( data flow 그래프에서 가장 긴 path의 길이를 최소화 )
  - 전체 경로를 source 정점 -> sink 정점으로 표시 ( p )
  - len(p) : p의 길이
  - δ(p) : p에 있는 정점의 개수
  - P(G) : 그래프 G에 있는 모든 전체 경로 집합
  - 최적화 목표값 : $min max_{p∈P(G)}len(p)$ ( p의 경로의 최댓값을 최소화 )
    - 추가로, len(p) == 모든 가능한 placement에 걸친 데이터 처리 / 전송 latency의 합이므로, $X_{b_is_i}$를 포함하여 공식화 가능 $\underset{X}{\operatorname{\arg min}}\underset{p\in{P(G)}}{\operatorname{\max}} \sum_{i=1}^{\delta(p)}\sum_{s_i\in{S_i}} X_{b_is_i}{T_{b_is_i}^C} + \sum_{i=1}^{\delta(p)-1}\sum_{s_i\in{S_i}\\ s_{i'}\in{S_i'}} X_{b_is_i}X_{b_{i'}s_{i'}}T_{b_is_is_{i'}}^N$
      - $i$, $i’$ : 경로 p의 인접 정점 ( $i’ = i + 1$ )
      - $S_i$ : i번째 logic block을 설치할 수 있는 모든 공간의 집합
      - $T_{b_is_i}^C$ : i번째 블럭을 $s_i$에 설치 했을 때의 데이터 처리 시간
      - $T_{b_is_is_{i’}}^N$ : i번째 블럭과 i+1번째 블럭 사이의 데이터 전송 시간
        같은 위치 $s_i == s_{i’}$ 이라면 무시 가능 $T_{b_is_is_{i'}}^N = \begin{cases} \lceil{\frac{q_{ii'}}{r_{ii'k}}}\rceil t_{ii'k} & s_i\ne s_{i'}\\ 0 & s_i = s_{i'} \end{cases}$
        $q_{ii’}$ : edge에서 전송되어지는 data size
        $r_{ii’k}$ : 프로토콜 k의 최대 패킷 payload를 나타내는 프로토콜 고유 metric
        $t_{ii’k}$ : 각 패킷 전송 시간 ( 네트워크 profiler에 의해 측정 / 예측 )
      - 위의 방정식 : Quadratic max/min problem ( NP-Hard 문제 )
        첨단 기술 : 휴리스틱 방식으로 해결
        최근 연구 : 그리디 bfs 알고리즘을 utilize
        반면, local 최적에 덜 노출되어지는 solver를 사용하는 것을 선호
        방정식을 재공식화하여 integer programming problem으로 재구성 ( lp_solve 등의 standard solver로 해결 가능한 문제 )
        $\epsilon_{is_is_{i’}}=X_{b_is_i}\cdot X_{b_{i’}s_{i’}}$ : quadratic 목적함수 -> 선형함수로 변환하여주는 보조변수
        이것이 존재하는 경우, 다음과 같은 제약조건 도입 $\begin{aligned} \epsilon_{is_is_{i'}} &\geq 0 \\ \epsilon_{is_is_{i'}} &\leq X_{b_is_i} \\ \epsilon_{is_is_{i'}} &\leq X_{b_{i'}s_{i'}}\\ \epsilon_{is_is_{i'}} + 1 &\geq X_{b_is_i} + X_{b_{i'}s_{i'}} \\ \text{when } (\forall{i\in\delta(p)-1, s_i\in S_i, s_{i'}\in S_{i'}}) \end{aligned}$
        4개의 제약조건은 모두 linear함
        여전히 minmax 문제이므로, max 함수를 대표하는 보조변수 z를 선언
        z -> 제약조건의 set으로 변경하여 표준 ILP 공식을 따르도록 함
        재작성된 목적함수는 아래와 같음 $\text{Objective: } \underset{X}{\operatorname{arg min}} z$
        \[\text{Subjective: } z\geq \sum_{i=1}^{\delta(p)}\sum_{s_i\in{S_i}} X_{b_is_i}{T_{b_is_i}^C} + \sum_{i=1}^{\delta(p)-1}\sum_{s_i\in{S_i}\\s_{i'}\in{S_i'}} \epsilon_{is_is_{i'}} T_{b_is_is_{i'}}^N, \forall{p}\in{G}\]
        제약 추가 : 모든 logic block은 특정 device 하나에만 존재할 수 있다. $\sum_{s_i\in{S_i}} X_{b_is_i}=1, \forall{i}\in{p}\in{G}$
        So, 위의 모든 식들을 이용하여 계산한 Objective의 최적해가 input app의 최적 분할

C. Executable Generator

2개의 step으로 구성
- 최적의 파티션과 logic block으로부터 컴파일 가능한 code의 조각을 구성하는 단계
- 플랫폼에 맞게 실행 가능하도록 code를 컴파일하는 단계
Contiki OS와 비슷하게, 감지 device뿐만 아니라 edge server에 대한 code도 생성할 수 있었음
- 각각 플랫폼에 맞는 toolchain으로 컴파일
- 처리해야할 유일한 차이점 : 다른 플랫폼에서 사용되어지는 다른 라이브러리 / 샘플링 API
- 초점 : 어떻게 컴파일 가능한 code를 효율적으로 실행되도록 생성할 것인지?
logic block : app의 building block 역할을 할만큼 표현 가능하도록 설계되어짐
- 최종 컴파일 가능한 code의 function으로 변환되어짐
- issue : 생성된 code에서 function call을 구성하는 방법?
  - 직관적인 접근법 ( event-driven kernel / Contiki OS의 protothread 기술을 수용하기 위함 ) : 같은 placement에 할당된 모든 logic block을 protothread 안에 배열한 후, 다음 block이 다른 device에 할당된 경우 데이터 주고받기
    - 간단하지만, 성능 면에서 단점이 있음 ( 설계상 protothread가 매우 길어질 수 있음 -> 시스템 성능 저하 )
    - 하나의 block당 하나의 protothread를 만드는 것 또한 효율적이지 못함
      - 짧은 protothread : 많은 process 전환 overhead 초래 -> 전체 makespan에 해악 초래
  - edgeprog의 접근법 : Contiki의 필수품인 code template / 수신 callback이 있는 send thread 기반 접근법
    - 기능적 protothread : 최적화된 유향 비순환그래프의 fragment로부터 생성
    - 각 device의 fragment : 배치 변화 지점에서 끝나는 그래프 dfs를 활용하여 얻을 수 있음
    - 이후 logic block의 함수를 호출하여 하나의 조각으로 protothread 조립
    - thread의 끝 : 데이터 전송을 위해 send thread에게 event 발생시킴
      - 다른 thread에게 yield
    - time profiling : 그래프 fragment는 system health를 위해 몇가지 시간소모적인 task를 포함하고 있다면, 더욱 세분화될 수 있음

Evaluation

A. Experiment Setup

5개의 macro-benchmark 사용할 것 ( 2개의 센싱 app / 3개의 real-world app )
- Sense : outlier detection / data 압축 등을 하는 일반적인 센싱 app
- MNSVG : 온도 / 습도를 예측하기 위해 MNSVG 모델을 사용하는 날씨 예측 app
- EEG : wishbone으로부터 취해진 seizure 감지를 위한 EEG signal 사용
  - 각 channel : 7차 wevelet 분해로 EEG 신호를 처리 ( 10개의 병렬채널 )
- SHOW : device의 궤적을 IMU 정보, 랜덤 forest 알고리즘 등으로 감지 / 분류
- Voice : 신호처리 / 분류 알고리즘 등을 이용하여 speaker 수를 셈

Baseline Definition

edgeprog와 비교할 첨단연구를 소개
- RT-IFFFF : 서버가 모든 연산 수행
  - 센서 : 값을 전달 / 실행만 함
- Wishbone(0.5, 0.5) : CPU / network 자원을 반반 쓰는 파티셔닝 시스템
- Wishbone(opt.) : CPU / network workload를 최소로 하는 상태의 파라미터를 사용하는 wishbone

B. Latency reduction

평균적으로 20.96% 감소 / 최대 99.05% 감소
2가지 주요 관찰결과
- 벤치마크에 따라 속도 상승률이 상당히 다름
  - 변화 원인 : 각 벤치마크의 계산복잡성 / 네트워크 요구량의 차이
- Zigbee 네트워크에서의 edgeprog 성능 > WIFI 네트워크에서의 edgeprog 성능
  - 가능한 모든 절단 지점에서 각 벤치마크를 철저히 실행함으로써 증명
  - 네트워크 속도 증가 = 데이터 전송시간 감소 / 데이터 처리에 시간을 지배적으로 사용
    - 최적화 알고리즘 : 초기에 작업을 offload하는 것을 선호
    - 따라서, WIFI에서의 전환점이 Zigbee보다 왼쪽에 존재함
      - 최적화 공간의 감소 의미 ( 기준선과 비슷한 성능 초래 )

C. Overhead

Disemination Overhead

알고리즘의 복잡성이 클수록 binary 크기가 증가
연산이 많아도 binary가 작은 경우가 있음
- 각 절차가 동일한 절차를 공유하기 때문 ( 주로 하나의 알고리즘 사용 )

Run-time efficiency

동적 링크 / 로딩 기술 runtime 효율성 측정 ( 가상머신 / 스크립팅 언어 )
결과
- VM을 사용하였을 때 실행시간은 매우 김
- edgeprog 언어를 사용하지 않았을 때보다 더 많은 실행시간 초래

D. Programming Language

Contiki 스타일 / Edgeprog 스타일 비교
결과
- edgeprog : 평균 79.41%의 line 감소 나타냄
  - 복잡한 장치간 상호작용 작성 완화 / 기타 문법 필수사항 작성 완화
  - 가상센서 / IFTTT 추상화 방법 또한 기여
- edgeprog : 더 많은 device가 포함된 app 개발의 복잡성 감소
  - 모든 장치에 대한 개별코딩이 필요하지 않기 때문

E. Profiling Accuracy

TelosB가 더 높은 정확도 달성
라즈베리파이가 정확도가 조금 불안정한 모습 ( CPU의 주파수 변동 / 라즈베리 파이의 배경 처리 기인 )

Conclusion

프로그램을 자동으로 분할 / 생성 / 보급 / 로드하는 EdgeProg 제안
- 개발자가 상세한 구현으로부터 완화될 수 있는 edge 중심 프로그래밍 시스템
개발자 / 비전문가에게 사용하기 쉽고 표현력이 좋은 프로그래밍 언어 제공
코드 파티셔너 : ILP 공식을 통해 응용프로그램의 각 부분에 대해 가장 효율적인 배치를 찾음
핵심 : 각 device의 계산 능력을 최대한 활용 / latency 감소 달성

EdgeProg: Edge-centric Programming for IoT Applications

Abstract

Introduction

Complex interactions

Intensive data processing

Background and EdgeProg Usage

A. Background

Dynamic linking and loading of IoT devices

Virtual sensor

B. EdgeProg Usage

EdgeProg Overview

A. Design Goals

Edge centric

Latency-aware

Automatic

B. EdgeProg Architecture

User Input

Code Partitioner

Time profiler

Network Profiler

Code Generator

Code Compiler

Loading Agent

System Design

A. EdgeProg Programming Language

Edge-centric programming model

Full support of virtual sensor

Explicit data flow

B. Code Partitioning

Logic blocks and data flow graph construction

The ILP problem for optimal partitioning

C. Executable Generator

Evaluation

A. Experiment Setup

Baseline Definition

B. Latency reduction

C. Overhead

Disemination Overhead

Run-time efficiency

D. Programming Language

E. Profiling Accuracy

Related Work

Conclusion

Further Reading

Marauder: Synergized Caching and Prefetching for Low-Risk Mobile App Acceleration

Pluto: High-Performance IoT-Aware Stream Processing

Multi-Task Federated Learning for Personalised Deep Neural Networks in Edge Computing