1 of 24

Nomad: Cross-Platform Computational Offloading and Migration in Femtoclouds Using WebAssembly

Mohammed Nurul-Hoque and Khaled A. Harras

2021 IEEE International Conference on Cloud Engineering

(IC2E’21)

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2 of 24

2

Importance of Migration in Edge Femtocloud Computing

모바일, IoT 및 기타 유휴 상태의 가정용 컴퓨팅 장치를 하나의 앙상블 또는 계산 풀로 활용�하는 새로운 형태의 엣지 컴퓨팅

일반적으로 가정용 장치나 IoT 장치와 같은 소형 장치들로 구성
이는 자원 부족으로 인한 성능 저하나 시스템 불안정성이 발생할 수 있음.
ex1) 사용자의 행동에 따라 전원이 꺼지거나 네트워크에서 분리될 수 있음.
ex2) 유휴상태가 해제되어 리소스가 부족해질 수 있음.

계산 부하를 오프로딩하고 적은 레이턴시를 달성하기 위해 노드 간에 �마이그레이션하는 능력은 엣지에서 필수적

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

3 of 24

3

Challenges in Heterogeneous Architecture Migration

CPU 호환성
서로 다른 CPU 아키텍처는 서로 다른 Instruction Set Architecture (ISA)를 사용.
메모리 레이아웃의 차이
메모리에서 데이터가 저장되는 방식에 차이를 가져와, 마이그레이션을 제한.
시스템 호출 및 하드웨어 접근
운영 체제는 시스템 호출을 통해 하드웨어 자원에 접근. �그러나, 시스템 호출은 아키텍처에 따라 다를 수 있음.
하드웨어 디바이스에 접근하는 방식도 아키텍처에 따라 다를 수 있음. �이는 서로 다른 하드웨어 인터페이스와 드라이버를 필요로 함.
컴파일러 및 바이너리 호환성
코드가 특정 아키텍처에서 컴파일될 때, 컴파일러는 해당 아키텍처에 최적화된 코드를 생성.
바이너리 파일 형식(예: ELF)은 아키텍처에 따라 다를 수 있으며, 이는 마이그레이션을 제한.

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

4 of 24

4

WebAssembly Overview

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

5 of 24

5

Can WebAssembly be migrated?

웹어셈블리 코드는 어디에서나 실행 가능
웹어셈블리 자체는 CPU 아키텍처에 종속적이지 않은 바이트코드 형식으로 설계
여러 언어로 작성된 코드를 컴파일하여 얻은 웹어셈블리 모듈은 어디서든 동일하게 동작
런타임 자체는 아키텍처에 종속됨 → 마이그레이션 불가
런타임은 웹어셈블리 모듈을 로드하고 실행하는 역할
각 웹어셈블리 런타임은 특정 CPU 아키텍처와 운영체제에 최적화되어 있을 수 있음

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

6 of 24

6

NOMAD System Architecture

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

7 of 24

7

Key Modifications to the NOMAD Interpreter

프로그램 상태는 실행 중에 변경되는 요소로, 마이그레이션 중 상태 덤프 파일에 기록
글로벌 변수, 메모리(힙), 값 스택, 가상 레지스터 및 가상 호출 스택

기존 wasm3에서는 호출 스택이 네이티브 스택에 암묵적으로 존재
시스템 종속적이며 프로그래밍적으로 접근하기 어려움
가상 호출 스택으로 대체하여 마이그레이션 시 직렬화할 수 있도록 수정

네이티브 레지스터 대신 가상 레지스터를 사용하여 프로그램의 상태를 관리

Program State Engine Migrator

Memory Layout

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

호출 스택은 함수 호출의 상태를 관리하는 데이터 구조입니다. 각 함수 호출 시, 현재 함수의 상태(예: 로컬 변수, 리턴 주소 등)가 스택 프레임으로 저장되고, 함수 호출이 종료되면 스택 프레임이 제거됩니다. 이는 함수 호출의 흐름을 관리하는 중요한 역할을 합니다.

스택 세그먼트에는 호출 스택 외, 함수 호출과 직접 관련이 없는, 중간 연산 결과나 컴파일러가 생성한 임시 데이터, 예외 처리 데이터 등도 저장될 수 있음.

Nomad 런타임에서는 네이티브 스택과 가상 호출 스택이 동시에 사용됩니다. 가상 호출 스택은 주로 함수 호출, 반환, 루프 처리 등의 프로그램 상태를 관리하는데 사용되지만, 네이티브 스택은 여전히 런타임 엔진의 실행 및 시스템 호출 등에서 사용

가상 레지스터와 네이티브 레지스터도 동시에 사용. 가상 레지스터는 프로그램 상태를 관리하고 마이그레이션을 지원하기 위해 존재하며, 실제 연산은 CPU의 네이티브 레지스터에서 수행

8 of 24

8

엔진함수 호출과 반환 시 가상 호출 스택을 사용하도록 수정

각 엔진 함수는 wasm3 가상 레지스터를 매개변수로 받도록 수정

루프 처리 방식 수정
wasm3에서 루프는 네이티브 스택을 사용하므로 가상 스택을 사용하도록 함

다양한 플랫폼에서 tail-call optimization (TCO)를 보장하기 위한 수정
Windows에서 TCO를 보장하기 위해 엔진 함수의 매개변수 순서를 변경
Windows에서 clang이 TCO를 수행할 수 없게 만드는 일부 엔진 함수 내부의 연산을 수정

Program State Engine Migrator

Key Modifications to the NOMAD Interpreter

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

9 of 24

9

Program State Engine Migrator

Key Modifications to the NOMAD Interpreter

실행 중인 프로그램에서 상태 덤프를 생성

상태 덤프에서 프로그램을 재개

절대 포인터와 상대 포인터 간의 변환

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

10 of 24

10

Program State Engine Migrator

Key Modifications to the NOMAD Interpreter

Migration in Nomad

인터프리터의 엔진 함수에서 확인하는 플래그 설정

플래그가 확인되면, 함수는 다음 연산을 호출하는 대신 State Writer로 제어를 전달

프로그램 상태의 구성 요소를 상태 덤프 파일로 직렬화

대상 시스템에서 State Reader가 덤프 파일에서 상태를 재구성하고 WebAssembly 파일을 IR로 다시 컴파일

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

11 of 24

11

Detail of Pointer Serializer

절대 포인터와 상대 포인터 간의 변환을 수행

가상 호출 스택은 실제 반환 주소에 대한 포인터를 저장
함수와 같은 객체들은 각기 다른 머신에서 다른 주소를 가질 수 있어 절대 포인터는 마이그레이션 불가

컴파일러에 후크를 삽입하여 브리지 테이블을 만듦

스니펫(Snippet) - 함수의 연속적인 코드 블록
브리지(Bridge) - 스니펫 간의 연결을 나타내는 구조체
브리지 테이블(Bridge Table) - 스니펫 간의 연결 정보를 가진 테이블

Snippet Example

Absolute Pointer: 메모리 내의 특정 위치를 가리키는 고정된 주소 ex) 0x7fff0000

Relative Pointer: base address로부터의 offset을 나타내는 주소 ex) 기준 주소 + 0x100

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

12 of 24

12

Detail of State Writer

직접 값 기록:

전역 변수, 메모리, 값 스택은 단순한 값이므로 직접 기록.

상대 포인터 변환:

프로그램 카운터(pc)를 상대적인 값으로 변환.
모든 가상 레지스터를 파일에 기록. 이때, 스택 포인터(sp)와 호출 스택 포인터(cs)는 기준 주소에서 뺀 값을 기록.

호출 스택 프레임 변환:

호출 스택의 각 프레임을 반복하면서, 각 프레임의 프로그램 카운터(pc)와 이전 프레임의 스택 베이스(bp)를 상대 포인터로 변환하여 기록.

Absolute Pointer: 메모리 내의 특정 위치를 가리키는 고정된 주소 ex) 0x7fff0000

Relative Pointer: base address로부터의 offset을 나타내는 주소 ex) 기준 주소 + 0x100

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

13 of 24

13

Detail of State Reader

상태 복원:

상태 덤프 파일을 읽어 프로그램 상태를 복원.
프로그램 카운터(pc)를 포함한 모든 가상 레지스터를 복원.

함수 미리 컴파일:

호출 스택의 함수와 프로그램 카운터(pc)에 해당하는 함수를 미리 컴파일. 이를 통해 절대 주소를 재구성.
함수 컴파일 시 브리지 테이블이 변경되므로, 이를 pointer serializer 에서 정렬.

이중 패스 처리:

첫 번째 패스에서는 상대 포인터를 읽고 함수를 컴파일.
두 번째 패스에서는 브리지를 정렬하고 모든 포인터를 변환.

프로그램 재개:

프로그램 카운터(pc)로 점프하여 프로그램 실행을 재개.

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

14 of 24

14

네이티브 종속성 제거:

네이티브 호출 스택 대신 가상 호출 스택을 사용
네이티브 레지스터 대신 가상 레지스터 사용

마이그레이션을 위한 상대 포인터 계산:

절대 포인터는 마이그레이션할 수 없으므로 상대포인터로 변환하여 마이그레이션.
복원 시 호출 스택의 함수와 프로그램 카운터(pc)에 해당하는 함수를 미리 컴파일. �이를 통해 절대 주소를 재구성.

Migrator 추가:
프로그램 상태를 덤프 파일로 직렬화 및 복원

tail-call optimization 개선

Summary of NOMAD's Modifications

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

15 of 24

15

Evaluation setup

Experimental Testbed

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

16 of 24

16

Evaluation setup

Benchmark Programs

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

17 of 24

17

Overhead

Nomad overhead over wasm3

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

18 of 24

18

Post-migration performance

Performance post-migration

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

19 of 24

19

Nomad fixed costs

Additional time costs

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

20 of 24

20

Cross-migration

Execution delay with cross migration

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

21 of 24

21

Limitations - The Slower Speed Compared to Native

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

22 of 24

22

Limitations - The Slower Speed Compared to Native

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

23 of 24

23

Limitations – WASI and Native Library Usage Not Considered

WebAssembly System Interface (WASI):

WebAssembly 모듈이 운영 체제의 기능과 상호작용할 수 있도록 하는 표준 인터페이스
WebAssembly 모듈이 파일 시스템, 네트워크, 시간, 환경 변수 등의 시스템 리소스에 접근할 수 있게함
접근중인 파일, 네트워크에 대한 마이그레이션은 보장되지 않음

Foreign Function Interface (FFI):

FFI는 서로 다른 프로그래밍 언어로 작성된 코드 간의 상호 호출을 가능하게 하는 인터페이스
WebAssembly 모듈에서 네이티브 라이브러리를 호출할 수 있음
네이티브 라이브러리를 사용하는 워크로드의 경우 여전히 호환성에 문제가 있음

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

24 of 24

24

Conclusion

호환성 문제를 펨토클라우드로의 계산 오프로딩의 핵심 문제로 제시

기존 인터프리터(wasm3)를 수정하여 마이그레이션을 지원하는 인터프리터 기반 시스템인 Nomad를 개발

WebAssembly에 어떠한 변경도 가하지 않으며, 순수하게 사용자 공간에서 작동하는 시스템

Nomad는 wasm3에 비해 큰 오버헤드를 추가하지 않으며, 마이그레이션된 코드가 비마이그레이션된 코드만큼 효율적으로 실행됨을 확인

서로 다른 운영 체제와 하드웨어 아키텍처를 가진 장치들 간의 크로스 플랫폼 마이그레이션을 성공적으로 테스트
현재의 컨테이너와 같은 기술이 호환할 수 있는 범위를 초과

인터프리터 속도는 일반적으로 네이티브 컴파일된 속도보다 훨씬 느리기 때문에 여전히 많은 개선의 여지가 있음

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY

2024-07-11 DDPS Seminar, Presenter Lim JunHo

Distributed Data Processing System Lab, KOOKMIN UNIVERSITY