GH.

My profile picture
WebGPU 활용해 보기: 그래프 시각화 대표 이미지

WebGPU 활용해 보기: 그래프 시각화

2025. 12. 14.

최근 WebGPU를 프론트엔드 실무에서 활용할 여지가 있는지 이리저리 실험해보고 있는 중이다. 그러던 차에 범용 계산 용도인 Compute Shader를 어떻게 활용하면 좋을까 생각했다.

과거 블록체인 회사에 재직했던 경험 덕분에 금융 도메인에서 자주 쓰이는 차트와 그래프 같은 시각화 기법이 떠올랐다. 아무래도 Compute Shader는 대규모의 단순 반복 계산에 효과적이고, 대규모 데이터를 특정 알고리즘에 따라 시각화하는 작업에 효과적일 수 있겠다는 생각이 들었다.

익숙한 데이터로 실험하기 위해 이더리움의 특정 블록 송금 데이터를 선택했다. 이 글에서는 이더리움 송금 데이터를 바탕으로 Cytoscape.js와 WebGPU를 활용해서 시각화하는 과정을 기록해본다.

데이터셋은 Kaggle에 공개되어 있는 것을 활용했다.

이더리움 송금 데이터의 구조는 간단하다. 일반적인 은행 송금과 비슷하게 송금자, 수신자, 금액 정보를 담고 있다. 차이점이라면 송금 시간 대신 블록 넘버로 정확한 시점을 알 수 있다는 정도다.

TypeScript
// 이더리움 트랜잭션 데이터 구조 예시
export type Transaction = {
	from: string;
	to: string;
	blockNumber: number;
	timestamp: number;
	value: string;
};

블록체인의 트랜잭션에도 timestamp가 있지만, 이는 블록 생성 시점의 대략적인 추정치로 정확한 시간 측정용이 아닌 참고용에 가깝다.

이 데이터로 무엇을 분석할지 고민한 끝에, 송금 흐름을 추적해보기로 결정했다. 송금 내역의 각 주소는 송금자와 수신자로 1:1 매칭된다. 이러한 데이터 구조에서는 어느 특정 이더리움 계정 주소로 송금이 몰리는 현상을 한 눈에 발견할 수 있는데, 이럴 때 사용할 수 있는 것이 Force-directed 계열의 레이아웃이다.

레이아웃(Layout)은 데이터의 구조와 관계가 드러나도록 그래프 요소들의 위치를 계산하는 방법을 의미한다.

Force-directed 계열 레이아웃

Force-directed 계열의 레이아웃은 노드(Node)와 엣지(Edge)를 이용해 그래프를 정리해 보여주는 방식이다. 노드들은 겹치지 않도록 퍼지려 하고, 엣지를 통해 연결된 노드들은 서로 가까이 유지되려 하면서, 전체 구조가 한눈에 이해되도록 배치된다.

말로 설명하는 것보다 그림으로 보는 것이 이해하기 쉬울 것이다.

엣지가 집중적으로 연결된 노드를 중심으로 뭉치는 경향이 있다. 이를 통해 특정 패턴을 시각적으로 파악할 수 있다. 예를 들어, 이 글에서 사용할 이더리움 송금 데이터에서는 특정 계정 주소로 자금이 집중되는 현상을 한눈에 발견할 수 있다.

Force-directed 계열에는 다양한 레이아웃이 있다. 이 글에서는 CoSE 레이아웃을 사용한다. CoSE는 Compound Spring Embedder의 줄임말로 Force-directed 레이아웃을 확장해, 여러 노드를 하나의 그룹처럼 묶어서 배치할 수 있도록 만든 알고리즘이다. 같은 그룹에 속한 노드들은 함께 움직이며, 그룹 간의 관계도 자연스럽게 드러나도록 전체 구조를 정리해준다.

다만, CoSE는 노드의 수가 늘어날수록 기하급수적으로 연산량이 증가한다. 특히 JavaScript 환경에서는 메인 스레드 병목을 크게 유발할 것이다. 이러한 한계를 보완하기 위해 CoSE-Bilkent와 FCoSE 같은 개선된 레이아웃이 등장했다.

Cytoscape.js 라이브러리를 활용하여 CoSE와 CoSE-Bilkent, FCoSE 레이아웃의 결과물을 비교해볼 예정이다. 그리고 마지막으로 CoSE를 Compute Shader로 유사하게 구현해보면서 실질적인 개선 효과가 나타날지 확인해볼 것이다.

Force-directed 원리

CoSE 레이아웃 구현에 앞서 CoSE의 근간이 되는 Force-directed 레이아웃의 핵심 원리를 살펴보자. 수포자인 필자도 이해한 쉬운 수학을 통해 최소한으로 소개해보겠다. 원리 설명이 필요 없거나 수학이 지루한 독자는 건너뛰어도 무방하다.

Force-directed 레이아웃은 물리 시뮬레이션을 통해 그래프의 노드를 자연스럽게 배치하는 알고리즘이다. 크게 스프링력(Spring Force)과 반발력(Repulsion Force)이라는 두 가지 힘으로 구성된다.

스프링력

스프링력은 엣지(Edge)로 연결된 노드 사이의 힘이다. 엣지란 노드 간의 연결선을 의미한다. 스프링력은 두 노드가 적절한 거리를 유지하도록 만든다.

먼저 두 노드 사이의 거리를 계산해야 한다. 필요한 지식은 사칙연산과 피타고라스 정리가 전부다.

TypeScript
const dx = b.x - a.x;
const dy = b.y - a.y;
const distance = Math.sqrt(dx * dx + dy * dy);

다음으로 단위 벡터(Unit Vector)를 구한다. 단위 벡터는 방향은 유지하되 크기가 1인 벡터로, 힘의 방향을 나타낸다.

TypeScript
const ux = dx / distance;
const uy = dy / distance;

스프링력은 훅의 법칙(Hooke's Law)을 단순화하여 계산한다. 두 노드 사이의 실제 거리와 이상적 거리의 차이에 비례하는 힘이 작용한다.

TypeScript
const idealLength = 80;
const k = 0.1;
 
const force = k * (distance - idealLength);
  • idealLength: 두 노드가 유지해야 할 이상적인 거리
  • k: 스프링 상수

distance 는 앞서 계산한 결과를 사용한다. k와 idealLength는 사용자 혹은 엔지니어가 직접 정해주면 된다. 두 노드의 거리를 더 벌리고 싶으면 idealLength 을 더 크게 조정하는 방식이다. k 는 커질수록 같은 조건 하에 스프링이 노드를 끌어당기는 힘이 강해진다. 두 상수를 GUI를 통해 사용자가 직접 조정하도록 제공해도 된다.

distance 와 idealLength 사이의 관계는 아래와 같다.

  • distance > idealLength: 양수 → 끌어당김
  • distance < idealLength: 음수 → 밀어냄

스프링력 벡터 계산

앞서 계산한 단위 벡터와 스프링력을 이용하여 스프링력 벡터를 구한다. 앞서 벡터는 힘의 방향을 나타낸다고 했었는데, 스프링력 벡터는 말 그대로 스프링의 힘과 방향을 모두 나타내는 벡터다.

TypeScript
const fx = ux * force;
const fy = uy * force;

노드 위치 업데이트

스프링력 벡터를 활용하여 각 노드 a 와 b 의 위치를 업데이트한다.

TypeScript
// 노드 a는 힘의 방향으로 이동
a.x += fx;
a.y += fy;
 
// 노드 b는 반대 방향으로 이동
b.x -= fx;
b.y -= fy;

스프링력 전체 코드

이제까지 살펴본 계산 단계를 통합한 코드다.

TypeScript
const dx = b.x - a.x;
const dy = b.y - a.y;
const dist = Math.sqrt(dx * dx + dy * dy) || 0.0001;
 
const ux = dx / dist;
const uy = dy / dist;
 
const idealLength = 80;
const k = 0.1;
 
// 엣지로 연결된 두 노드 사이의 스프링력
const force = k * (dist - idealLength); 
 
// 스프링력에 방향을 추가한 스프링력 벡터
const fx = ux * force;
const fy = uy * force;
 
a.x += fx;
a.y += fy;
b.x -= fx;
b.y -= fy;

dist 에 0.0001 을 주는 이유는 두 노드 사이의 거리가 완전히 동일하면 안되므로 작은 값으로 최소 거리를 보장한다.

이 코드만으로도 엣지로 연결된 노드들이 자연스럽게 배열되는 효과를 얻을 수 있다. 하지만 노드 간 겹침을 방지하려면 반발력이 추가로 필요하다.

반발력

스프링력과 달리 반발력은 모든 노드 쌍 사이에 작용하는 척력이다. 엣지로 연결되지 않은 노드 간에도 적용되어 노드들이 서로 겹치지 않도록 밀어낸다.

반발력은 거리의 제곱에 반비례한다. 이는 쿨롱의 법칙(Coulomb's law)과 유사한 형태다.

TypeScript
force = c / distance^2
  • c: 반발력 상수
  • distance: 거리
  • force: 반발력

반발력 상수는 0보다 큰 상수다. 스프링 상수와 마찬가지로 사용자 혹은 엔지니어가 직접 정하면 된다. 거리가 가까울수록 반발력은 급격히 증가한다. 최소 거리를 보장하기 때문에 반발력은 항상 양수다.

반발력 벡터

반발력 벡터는 스프링력과 유사하게 단위 벡터를 활용하여 다음과 같이 계산된다.

TypeScript
fx = ux * (C / distance^2)
fy = uy * (C / distance^2)

반발력 전체 코드

아래는 반발력을 적용하는 전체 코드다.

TypeScript
const dx = a.x - b.x;  // 주의: b → a 방향 (스프링과 반대)
const dy = a.y - b.y;
 
const distSq = dx * dx + dy * dy + 0.0001;
const dist = Math.sqrt(distSq);
 
const ux = dx / dist;
const uy = dy / dist;
 
const C = 500;  // 반발력 계수
const force = C / distSq;
 
const fx = ux * force;
const fy = uy * force;
 
a.x += fx;  // a는 b로부터 멀어짐
a.y += fy;
b.x -= fx;  // b는 a로부터 멀어짐
b.y -= fy;

스프링력의 전체 코드와 크게 다르지 않은데, 주의할 것은 반발력은 스프링과 서로 반대 방향으로 적용되는 힘이므로 거리를 구할 때 노드의 순서를 반대로 해야한다.

Force-directed 레이아웃 시뮬레이션

지금까지 두 노드 사이에 작용하는 기본 힘을 살펴보았다. 이제 전체 그래프에 이를 어떻게 적용하는지 알아보자. Force-directed에서는 한 번의 이터레이션에서 아래와 같은 작업을 수행한다.

  • 모든 노드 쌍에 대해서 반발력 계산 및 적용
  • 모든 엣지에 대해 스프링력 계산 및 적용

이 두 가지 힘만으로도 CoSE 알고리즘과 유사한 레이아웃을 구현할 수 있다. 하지만 현재 방식에는 문제가 있다. 계산한 힘을 노드 위치에 직접 적용하면 힘이 클 때 노드가 한 번에 과도하게 이동한다. 다음 이터레이션에서는 반대 방향의 큰 힘이 발생해 노드가 다시 크게 튀어난다. 부드러운 움직임 대신 급격한 진동이 반복되는 것이다.

이는 물리 법칙을 제대로 반영하지 못했기 때문이다. 실제 세계에서 힘은 위치를 직접 변경하지 않는다. 힘은 속도를 변경하고, 속도가 위치를 변경한다. 이 개념을 코드로 옮기면 다음과 같다.

TypeScript
vx = vx + Fx
vy = vy + Fy
 
x = x + vx
y = y + vy
  • F: 계산한 힘
  • v: 속도
  • x, y: 노드 위치

Fx와 Fy는 지금까지 구한 스프링력과 반발력을 의미한다. 이를 속도인 vx, vy에 더한다. 그리고 vx와 vy를 노드의 위치인 x와 y에 더하는 방식이다.

하지만 속도를 도입해도 또 다른 문제가 남는다. 매 이터레이션마다 힘이 속도에 계속 누적되므로, 노드가 적절한 위치에 도달해도 속도가 남아있어 멈추지 않는다. 시뮬레이션이 안정 상태에 수렴하지 못하고 영원히 진동할 수 있다.

실제 물리 세계를 생각해보면 답이 있다. 마찰력과 공기 저항이 존재하기 때문에 움직이던 물체도 결국 멈춘다. 이를 모델링하기 위해 감쇠(Damping)를 도입한다. 매 이터레이션마다 속도를 일정 비율로 감소시켜 노드가 점진적으로 안정 상태에 수렴하도록 만드는 것이다.

TypeScript
vx = vx * damping
vy = vy * damping
  • damping: 감쇠 상수
  • v: 속도

아래는 매 이터레이션마다 힘과 속도, 감쇠, 위치 업데이트를 모두 포함한 계산 예시다.

TypeScript
// 힘이 이미 fx, fy로 계산되었다고 가정
 
// 1. 힘을 속도에 적용
node.vx += fx;
node.vy += fy;
 
// 2. 감쇠 적용
node.vx *= 0.9;
node.vy *= 0.9;
 
// 3. 속도를 위치에 적용
node.x += node.vx;
node.y += node.vy;

스프링력과 반발력, 속도, 감쇠를 통합하면 최소한으로 구현된 Force-directed 레이아웃을 시뮬레이션해 볼 수 있다. 아래는 이 개념들을 활용하여 직접 만들어본 시뮬레이션 예제다.

Force Directed Layout Simulation

CoSE 레이아웃

지금까지 구현한 Force-directed 레이아웃은 기본적인 그래프 배치에는 유용하지만, 두 가지 한계가 있다. 노드를 그룹으로 묶어 표현하기 어렵고, 부모-자식 관계(Compound Nodes)를 나타낼 수 없다. 예를 들어 조직도나 파일 시스템처럼 계층 구조를 가진 데이터를 시각화하기에는 부족하다.

CoSE(Compound Spring Embedder)는 Force-directed 레이아웃을 확장하여 이 문제를 해결했다. 두 가지 핵심 기능을 제공한다.

첫째, Component Separation이다. 엣지로 연결된 노드들을 하나의 컴포넌트로 인식하고, 이를 바운딩 박스(Bounding Box, 요소를 감싸는 최소 사각형)로 묶는다. 독립된 그래프 조각들을 시각적으로 분리하여 보여줄 수 있다.

둘째, Compound Nodes다. 부모-자식 관계를 지원하여 계층 구조를 표현할 수 있다. 자식 노드들이 부모 노드 안에 포함되는 방식이다.

이 글에서 사용하는 이더리움 송금 데이터는 계층 구조가 없는 평면 그래프이므로 라이브러리 내부적으로 Component Separation 기능만을 사용하게 된다. CoSE는 컴포넌트의 크기를 계산한 뒤, 큰 바운딩 박스부터 상단에 배치하는 방식으로 전체 레이아웃을 정리한다.

실제로 Cytoscape.js의 CoSE 구현을 살펴보면 Component Separation의 작동 원리를 확인할 수 있다.

JavaScript
var totalA = 0;
 
for (var i = 0; i < components.length; i++) {
	var c = components[i];
	
	if (!c) {
		continue;
	}
 
	c.x1 = Infinity;
	c.x2 = -Infinity;
	c.y1 = Infinity;
	c.y2 = -Infinity;
 
	// 여러 노드로 이루어진 컴포넌트의 바운딩 박스 계산
	for(var j = 0; j < c.length; j++){
		var n = c[j];
		
		c.x1 = Math.min(c.x1, n.positionX - n.width / 2);
		c.x2 = Math.max(c.x2, n.positionX + n.width / 2);
		c.y1 = Math.min(c.y1, n.positionY - n.height / 2);
		c.y2 = Math.max(c.y2, n.positionY + n.height / 2);
	}
 
	// 최소`x1`와 최대`x2`값으로 컴포넌트의 최대 너비를 구하여 저장한다.
	// 최소`y1`와 최대`y2`값으로 컴포넌트의 최대 높이를 구하여 저장한다.
	c.w = c.x2 - c.x1;
	c.h = c.y2 - c.y1;
	
	// 모든 컴포넌트의 너비와 높이를 총 면적에 저장한다.
	totalA += c.w * c.h;
}

https://github.com/cytoscape/cytoscape.js/blob/unstable/src/extensions/layout/cose.mjs#L1276-L1301

  • components: 연결된 노드를 사전에 재귀적으로 탐색하여 그룹화한 컴포넌트의 묶음이다.
  • totalA: 모든 컴포넌트를 배치하는데 필요한 최소한의 총 면적이다.

각 컴포넌트의 모든 노드를 순회하며 최소/최대 x, y 좌표를 구해 바운딩 박스의 너비(c.w)와 높이(c.h)를 계산한다. 그런 다음 면적을 기준으로 내림차순 정렬한다.

JavaScript
components.sort(function(c1, c2){
	return c2.w * c2.h - c1.w * c1.h;
});

https://github.com/cytoscape/cytoscape.js/blob/unstable/src/extensions/layout/cose.mjs#L1303-L1305

이러한 과정을 거쳐 Cytoscape.js의 CoSE 레이아웃은 바인딩 박스로 묶인 노드들과 박스의 크기 순으로 정렬된 그래프를 볼 수 있다.

개선된 CoSE도 여전히 근본적인 문제를 안고 있다. Force-directed의 기본 원리를 따르기 때문에 모든 노드 쌍 사이의 반발력을 계산해야 한다. 시간 복잡도는 O(n^2)로 노드 수가 증가하면 연산량이 기하급수적으로 증가한다. 실제로 개발자 도구로 측정하면 심각한 메인 스레드 병목을 확인할 수 있다.

레이아웃 배치 시간이 1.85초 걸린다. 프로파일링 결과뿐만 아니라 실제 사용자 경험도 좋지 않다. 노드가 수백 개를 넘어가면 레이아웃 계산 중 브라우저가 멈춘 것처럼 느껴지는 일명 프리징이 발생한다. 이러한 한계를 극복하기 위해 개선된 알고리즘들이 등장했다.

CoSE-Bilkent 레이아웃

Cytoscape.js의 서드파티 확장 레이아웃으로 CoSE-Bilkent 라이브러리가 있다. CoSE-Bilkent는 CoSE 레이아웃을 개선하여 성능을 향상시킨 알고리즘이다. 참고로 Bilkent는 튀르키예의 앙카라에 위치한 빌켄트 대학교(Bilkent University)의 이름에서 따온 것이다.

아래는 CoSE-Bilkent를 사용한 프로파일링 결과다.

레이아웃 배치 시간이 0.23초로 메인 스레드 병목이 상당히 줄어든 것을 확인할 수 있다.

CoSE와 CoSE-Bilkent의 차이점은 몇 가지 있는데, 성능 최적화 관점에서 가장 큰 차이는 멀티 레벨 스케일링이라는 기능이 도입되었다. 멀티 레벨 스케일링을 활성화하면 큰 그래프를 단계적으로 축소하면서 레이아웃을 계산하여 더욱 빠른 수렴이 가능하다.

다만, 라이브러리에서 이 기능은 기본적으로 비활성 상태이고, 이 예제에서도 사용하지 않았다. 그럼에도 성능이 크게 개선된 이유가 궁금하여 내부 구현을 살펴보니, 또 다른 최적화 기법을 발견할 수 있었다.

CoSE-Bilkent는 CoSE 레이아웃를 기반으로 한다. 다만, 앞서 사용했던 Cytoscape.js에서 제공하는 CoSE 레이아웃 코드를 사용하지 않고, 자체적으로 만든 코드 베이스를 사용하는데 동일한 개념이 바탕이 되어있지만 최적화 부분에서 상당히 달랐다.

아래 코드는 반발력 범위(repulsionRange)로 전체 그래프 영역을 나누어 격자로 분할하는 코드다. 참고로 반발력 범위는 사용자가 설정한 노드 사이의 이상적인 거리(idealLength)에 비례한다.

JavaScript
FDLayout.prototype.calcGrid = function (graph){
	var sizeX = 0;
	var sizeY = 0;
	
	// X축 방향 격자 개수 계산
	sizeX = parseInt(Math.ceil((graph.getRight() - graph.getLeft()) / this.repulsionRange));
	// Y축 방향 격자 개수 계산
	sizeY = parseInt(Math.ceil((graph.getBottom() - graph.getTop()) / this.repulsionRange));
	
	// X축 방향 1차원 배열 생성
	var grid = new Array(sizeX);
 
	// 각 X 위치에 Y축 방향 배열 생성
	for(var i = 0; i < sizeX; i++){
		grid[i] = new Array(sizeY);
	}
	
	// 각 격자 셀을 빈 배열로 초기화
	for(var i = 0; i < sizeX; i++){
		for(var j = 0; j < sizeY; j++){
			grid[i][j] = new Array();
		}
	}
	
	// 생성된 2D 격자 반환
	return grid;
};

https://github.com/iVis-at-Bilkent/layout-base/blob/master/src/fd/FDLayout.js#L407-L428

노드 간 반발력을 연산하기 전에 전체 그래프 영역을 격자(Grid)로 분할하여 격자 내 노드끼리만 반발력을 계산한다. 이렇게 할 수 있는 이유는 실제 세계에서 노드 사이의 거리가 멀면 서로 밀치는 일이 발생하기 힘들다는 점에서 착안한 것으로 생각한다. 마치 비유하자면 지구 반대편 사람과는 서로 밀칠 수 없는 것이다.

이 격자 기반 최적화 덕분에 시간 복잡도는 기존 O(n^2)에서 O(n)에 가깝게 개선된다. (여기서 n은 노드 수, 격자당 평균 노드 수는 상수로 취급) 프로파일링 결과에서도 측정 시간을 살펴보면 시간 복잡도와 유사한 결과를 나타내는 것을 확인해볼 수 있다.

앞서 CoSE와의 결과물과는 노드 배치가 사뭇 다르지만, 연산 속도가 훨씬 빨라서 실질적으로 사용해볼 수 있는 그래프가 되었다.

fCoSE 레이아웃

fCoSE는 CoSE와 CoSE-Bilkent를 개선한 버전이다. Cytoscape.js의 서드파티 확장으로 fCoSE 라이브러리가 있다. 앞서 두 레이아웃과 가장 큰 차이는 스펙트럴 초기화(Spectral Initialization)라고 하는 초기 노드 배치 단계가 추가된다는 점이다. CoSE와 CoSE-Bilkent는 노드를 무작위로 배치한 뒤 반복 계산으로 최적 위치를 찾아가지만, fCoSE는 그래프 구조를 미리 분석하여 더 나은 초기 위치에서 시작한다.

fCoSE에서는 스펙트럴 초기화에 거리 행렬 기반의 다차원 척도법(MDS, Multidimensional Scaling)이라는 알고리즘을 사용한다. 계산 과정을 요약해보면, 먼저 대표 노드 몇 개를 샘플링한다. 모든 노드를 대상으로 계산하면 비용이 크기 때문에 그래프를 대표할 수 있는 일부 노드만 선택하는 것이다. 다음으로 모든 노드와 대표 노드 사이의 거리를 행렬에 기록하여 거리 행렬을 만든다. 이때 BFS(너비 우선 탐색)가 활용된다. BFS로 최단 경로를 추적하면서 각 노드가 대표 노드로부터 얼마나 떨어져 있는지 계산하는 방식이다.

이렇게 만든 거리 행렬은 정사각형이 아닐 수 있다. 전체 노드 수와 샘플링된 대표 노드 수가 다르기 때문이다. 그러므로 이에 맞는 의사역행렬(Pseudoinverse)을 구한다. 의사역행렬은 정사각 행렬이 아닌 경우에도 역행렬과 유사한 역할을 할 수 있도록 만든 개념이다. 마지막으로 거리 행렬과 의사역행렬을 서로 곱하여 각 노드의 최종 2D 좌표를 구한다. 이 좌표가 각 노드의 초기 위치가 된다.

솔직히 말하면 fCoSE의 수학적 원리는 다른 레이아웃보다 복잡한 편이고 논문으로는 이해하기 어려웠다. 그래서 논문 대신 라이브러리 코드를 통해 큰 틀에서의 계산 과정만 유추했다. 결과적으로 fCoSE의 시간 복잡도도 O(n)에 가깝다.

약 0.39초로 이 예제 기준으로는 CoSE와 큰 격차의 시간 차이지만, CoSE-Bilkent와는 차이가 크지 않고 오히려 소폭 늘었다. 원인은 이더리움 송금 데이터가 상대적으로 단순한 구조이기 때문으로 추측되는데, 더 복잡한 관계를 가진 데이터 셋에서는 fCoSE의 스펙트럴 초기화가 더 큰 성능 향상을 보일 수도 있겠다.

WebGPU로 구현한 CoSE

지금까지 살펴본 세 가지 레이아웃은 모두 나름의 최적화를 통해 성능을 개선했다. 하지만 이 글의 원래 목적은 WebGPU Compute Shader를 실무에서 활용할 수 있는지 실험해보는 것이었다. 그래서 Cytoscape.js의 CoSE를 직접 개선해보기로 했다.

CoSE의 여러 계산 단계 중 어느 부분을 GPU로 옮길지 고민한 끝에, 시간 복잡도를 O(n^2)로 만드는 핵심 원인인 반발력 계산만 WebGPU의 Compute Shader에게 맡기기로 했다. 계산 방식 자체는 앞서 살펴본 CoSE의 반발력 공식과 동일하다. 다만 모든 노드 쌍 사이의 반발력을 CPU가 순차적으로 계산하는 대신, GPU가 병렬로 처리하도록 변경했다. 스프링력 계산과 노드 위치 업데이트 등 나머지 로직은 기존 JavaScript 코드를 TypeScript로 변환하여 사용했다.

프로파일링 결과를 보면 약 0.4초로 기존 CoSE와는 큰 격차의 시간 차이가 나고,CoSE-Bilkent와 fCoSE와 유사한 수준의 성능을 보인다. 알고리즘 자체는 개선하지 않았기 때문에 CoSE-Bilkent나 fCoSE처럼 O(n)에 가까운 시간 복잡도를 달성한 것은 아니다. 하지만 GPU의 병렬 연산 능력 덕분에 O(n^2) 계산이 실용적인 시간 안에 완료될 수 있었다.

또한, 플레임 그래프를 보면 앞서 다른 알고리즘과 다르게 GPU 연산이 늘고, 메인 스레드의 작업이 잘게 쪼개져서 idle 시간이 많이 생긴 것을 확인할 수 있다.

앞서 보았던 CoSE와 노드 배치가 달라서 예쁘지는 않다. 노드 배치에 대해 시각적인 계산 조정이 필요하지만 전체적인 구조는 유사하다.

WGSL
fn compute_repulsion(@builtin(global_invocation_id) gid: vec3<u32>) {
	let i = gid.x;
	
	(...)
	
	let nodeA = nodes[i];
	var j: u32 = 0u;
 
	loop {
		let nodeB = nodes[j];
		
		(...)
 
		// 노드가 차지하고 있는 영역의 가장자리에서 반발력 계산
		let p1 = find_clipping_point(nodeA.x, nodeA.y, nodeA.width, nodeA.height, dx, dy);
		let p2 = find_clipping_point(nodeB.x, nodeB.y, nodeB.width, nodeB.height, -dx, -dy);
		
		// 거리 계산
		let distX = p2.x - p1.x;
		let distY = p2.y - p1.y;
 
		let distSq = distX * distX + distY * distY + 1e-4;
		let dist = sqrt(distSq);
		
		// 반발력 계산
		let force = (nodeA.repulsion + nodeB.repulsion) / distSq;
 
		// 반발력 벡터 계산 및 누적
		fx -= (force * distX) / dist;
		fy -= (force * distY) / dist;
 
		(...)
	}
	(...)
}

WGSL로 작성한 Compute Shader 코드 일부다. 많은 부분을 생략했지만, 루프 내의 반발력 계산의 핵심 로직은 앞서 살펴본 반발력 전체 코드와 유사하다.

큰 개선은 아니지만, WebGPU Compute Shader가 유의미한 결과를 준다는 것에 의의를 둔다. 특히 흥미로웠던 점은 CPU와 GPU 사이의 데이터 전송이 성능 병목을 일으킬 수 있겠다고 생각했는데, 실제로 그런 이슈는 없었다. 매 이터레이션마다 노드 위치 데이터를 GPU로 전송하고 결과를 다시 받아오는 과정이 있지만, GPU의 연산 속도가 데이터 전송 비용을 충분히 상쇄했다.

마치며

이 글에서는 Force-directed 레이아웃의 성능 문제를 WebGPU Compute Shader로 해결할 수 있는지 실험해보았다. Cytoscape.js의 CoSE 레이아웃에서 O(n^2) 병목을 일으키는 반발력 계산을 GPU에게 맡긴 결과, CoSE-Bilkent나 fCoSE 같은 알고리즘 최적화 없이도 실용적인 성능을 얻을 수 있었다.

WebGPU Compute Shader가 프론트엔드 실무에서 활용 가능한지에 대한 내 생각은 "가능은 하다"이다. 다만, 모든 계산을 GPU로 옮기는 것이 능사는 아니다. 이번 실험에서도 전체 레이아웃 알고리즘을 GPU로 구현하는 대신, 병목이 되는 특정 계산만 선택적으로 맡겼다. CPU와 GPU 사이의 데이터 전송 비용을 고려하되, 충분한 연산량이 있는 작업이라면 GPU의 병렬 처리 능력이 이를 상쇄할 수 있다.

싱글 스레드 병목을 해소하기 위해 Web Workers를 활용하는 방법도 있지만, WebGPU와는 최적화 맥락이 다르다. Web Workers는 별도 스레드를 활용하여 비동기적으로 처리할 수 있으므로 프리징이 발생하지 않도록 사용자 경험 측면에서 개선의 여지가 있지만, 단일 알고리즘에 대한 근본적인 연산 속도는 해결하지 못한다. 결국 CPU 연산에 의존하기 때문이다. 반면 WebGPU는 GPU를 활용한 병렬 연산을 통해 이를 개선할 수 있다.

실무에서 시도해보려면 당연하게도 구성원의 합의가 필요하다. 브라우저 호환성 문제와 WebGPU API의 복잡성, 유지보수 측면에서도 WGSL 코드를 추가하는 것이 장기적으로 도움이 될지 신중히 판단해야 한다.

긍정적으로 볼 여지도 있다. 특히 AI로 인해 WGSL 코드 생성이 점점 쉬워지고 있기 때문이다. 필자도 이 예제를 만들면서 레이아웃 계산에 대한 의사 코드를 프롬프트 파일로 정리하고 Compute Shader로 최적화할 구체적인 영역을 컨텍스트에 포함시켜 AI에게 WGSL 코드를 생성하도록 시도했다. 생성한 결과물을 직접 터치하는 과정이 필요하므로 완벽하지는 않지만, 앞으로 가능성은 충분히 있어 보인다.

GPU 프로그래밍의 진입 장벽이 낮아진다면 WebGPU는 프론트엔드에서 고성능 연산을 가능하게 하는 현실적인 선택지가 될 수도 있지 않을까.

References