수학과 계산

무작위 행렬 실험

난수로 채운 큰 행렬을 반복해서 대각화해, 고윳값의 통계를 연구해요.

답하는 질문: 무작위 행렬의 고윳값은 어떤 패턴으로 자리 잡을까, 그리고 그것은 수학과 물리의 다른 분야와 맞아떨어질까?

빠진 것: 가능한 행렬의 무한한 공간 중 아주 작은 한구석만 표본으로 뽑아요.

돌아가는 곳: 약 10¹² FLOPS 대략 큰 행렬을 많이 만들고 대각화하는 대학 클러스터처음 등장: 1955 위그너의 무작위 행렬 고윳값 통계에 대한 초기 연구

무작위 그래프 실험

무작위 규칙으로 노드별 또는 간선별로 그래프를 만들어, 연결성이나 군집성 같은 어떤 성질이 보통 나타나는지 살펴봐요.

답하는 질문: 노드와 간선을 더하는 이 규칙 아래에서 ‘전형적인’ 네트워크는 어떤 모습일까?

빠진 것: 현실의 네트워크는 모델을 만드는 규칙만큼 깔끔한 경우가 거의 없어요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 데스크톱에서 최대 수백만 노드의 그래프까지 돌아가요처음 등장: 1959 Erdos와 Renyi의 무작위 그래프 모델

침투 시뮬레이션

격자나 네트워크의 자리나 연결을 무작위로 열어 가다가, 이어진 경로가 갑자기 시스템 전체를 가로지르는 지점을 지켜봐요.

답하는 질문: 무작위 네트워크는 밀도가 얼마일 때 갑자기 끝에서 끝까지 이어질까?

빠진 것: 이상화된 격자는 실제의 어떤 다공성 물질이나 네트워크보다 깔끔하게 움직여요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 대규모 격자 스윕을 위한 데스크톱 컴퓨터처음 등장: 1957 Broadbent와 Hammersley의 침투 이론 도입

실험 수학 탐색

숫자 사이의 패턴, 반례, 정확한 관계를 찾는 무차별 수치 탐색으로, 손으로 확인할 수 있는 범위를 훨씬 넘어서 돌려요.

답하는 질문: 이 추측은 계산으로 확인해 볼 수 있는 모든 경우에서 참일까요, 그리고 어떤 패턴이 드러날까요?

빠진 것: 아무리 많은 경우에서 성립한다고 확인해도 그 자체로는 증명이 아니에요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 탐색 하나에 며칠 동안 돌아가는 대학 클러스터처음 등장: 1963 1963년까지, 정수 관계와 소수 패턴을 찾는 컴퓨터 탐색

상수의 몬테카를로 추정

무작위 표집으로 수학 상수나 적분을 추정하는 일로, 영역의 넓이를 구하려고 점을 흩뿌리는 식이에요. 물리 모델이 아니라 연습으로 해요.

답하는 질문: 눈을 감고 하는 무작위 표집만으로 정확한 수학적 양에 얼마나 가깝게 다가갈 수 있을까요?

빠진 것: 거의 어떤 더 정교한 수치 방법보다도 훨씬 느리게 수렴해요.

돌아가는 곳: 약 10⁹ FLOPS 대략 노트북에서 몇 초에서 몇 분이면 돌아가요처음 등장: 1946 1946년 울람의 아이디어. 폰 노이만이 1947년 3월에 전자 컴퓨터 버전을 제안했고, 이 방법은 1949년에 처음 발표됐어요. 출처시뮬레이션 트리에서: 몬테카를로 방법

상호작용 모델 실행하기

계산 정수론 탐색

큰 수를 대상으로 소수 판별, 소인수분해, 완전수 같은 특별한 성질 찾기를 손이 아니라 대규모로 돌리는 알고리즘으로 해요.

답하는 질문: 이 거대한 수가 우리가 찾는 성질을 가질까요, 그리고 탐색이 기록을 얼마나 밀어붙일 수 있을까요?

빠진 것: 기록을 깨는 탐색은 아직 아무도 확인해 볼 생각을 하지 않은 수에 대해서는 알려 주는 것이 거의 없어요.

돌아가는 곳: 약 10¹³ FLOPS 대략 기부받은 수많은 기계에 걸친 분산 자원봉사 컴퓨팅 프로젝트처음 등장: 1951 뤼카의 메르센 소수 손 검사, 1951년에 처음으로 컴퓨터로 실행

혼돈 끌개 수치 계산

비선형 방정식 몇 개를 한 걸음씩 적분해, 초기 조건에 대한 민감한 의존성과 프랙털 끌개를 드러내요.

답하는 질문: 단순한 결정론적 시스템은 왜 예측할 수 없게 될까?

빠진 것: 수치 반올림 때문에 긴 궤적은 진짜 궤도가 아니라 진짜 궤도에 가까이 머무는 것일 뿐이에요.

돌아가는 곳: 약 10³ FLOPS 대략 방정식 몇 개, 노트북에서 몇 초.처음 등장: 1963 로렌츠의 결정론적 비주기 흐름, 컴퓨터로 돌린 대류 모델 출처시뮬레이션 트리에서: 로렌츠의 혼돈 대류

비선형 격자 실험

비선형 용수철로 이은 질량의 사슬을 한 가지 모드로 시작해 놓고, 열역학이 시사하듯 에너지가 고르게 퍼지는지 따라가요.

답하는 질문: 비선형 사슬이 에너지를 모든 운동에 고르게 나눌까요?

빠진 것: 결과는 선택한 사슬과 초기 상태에 달려 있어요.

돌아가는 곳: 약 10³ FLOPS 대략 오늘날 기준으로는 아주 작아요. 원래는 질량 수십 개를 썼어요.처음 등장: 1955 Fermi, Pasta, Ulam의 초기 디지털 컴퓨터를 이용한 비선형 문제 연구. 출처

솔리톤 수치 실험

비선형 파동 방정식을 격자 위에서 풀어, 펄스가 서로를 통과하고도 모양을 유지하는 모습을 봐요. 선형 파동은 그러지 못해요.

답하는 질문: 어떤 비선형 파동은 왜 서로를 그대로 통과할까?

빠진 것: 비선형 파동의 일반적인 거동이 아니라 방정식 한 계열만 보여 줘요.

돌아가는 곳: 약 10⁴ FLOPS 대략 1차원 격자, 오늘날엔 아주 쉬워요.처음 등장: 1965 자부스키와 크러스컬의 무충돌 플라즈마에서 솔리톤의 상호작용과 초기 상태의 재귀예요. 출처

프랙털 집합 렌더링

복소평면의 각 위치에서 단순한 반복 공식이 발산하는지 시험해, 안정한 점들의 집합의 경계를 그려요.

답하는 질문: 단순한 반복이 유한하게 머무는 집합은 어떤 모양일까?

빠진 것: 탈출 시험은 집합에 속한다는 것을 시사할 뿐이고, 그림은 무한히 세밀한 집합을 유한한 해상도로 표본 추출한 거예요.

돌아가는 곳: 약 10⁹ FLOPS 대략 깊이 확대하려면 수백만 개의 점에서 확장 정밀도 반복이 필요해요.처음 등장: 1980 Mandelbrot's fractal aspects of the iteration of z to lambda z(1-z), first computer images of the Mandelbrot set. 출처

모래더미 자기 조직 임계성

격자 위에 낟알을 떨어뜨리고 너무 가팔라지면 무너지게 해서, 따로 조정하지 않아도 온갖 크기의 눈사태가 생겨요. 시스템이 임계 상태에 이르는 과정을 보여 주는 모델이에요.

답하는 질문: 조정하지 않았는데도 왜 모든 크기의 눈사태가 나타날까?

빠진 것: 실제 시스템이 같은 스케일링을 따르는지는 논란이 있어요.

돌아가는 곳: 약 10⁹ FLOPS 대략 규모 변화를 보기 위한 큰 격자에서의 긴 실행.처음 등장: 1987 백, 탕, 비젠펠트의 자기 조직화 임계성: 1/f 잡음에 대한 설명. 출처

리만 제타 영점 계산

제타 함수의 임계선 위 값을 계산해서 그 영점을 찾아 세고, 가설이 말하는 곳에 있는지 확인해요.

답하는 질문: 제타 함수의 모든 비자명 영점은 한 직선 위에 있을까요?

빠진 것: 아무리 길어도 유한한 검사로는 그 너머에 선 밖의 영점이 없다는 것을 증명할 수 없어요.

돌아가는 곳: 약 10¹⁸ FLOPS 대략 가장 큰 탐색에는 수십 년의 CPU 시간.처음 등장: 1953 튜링의 리만 제타 함수 계산. 출처

컴퓨터로 구하는 원주율의 자릿수

원주율 급수를 정확한 산술로 엄청난 자릿수까지 합산해서, 그 수와 기계를 함께 시험해요.

답하는 질문: 원주율의 자릿수는 무작위로 보일까요, 그리고 이 규모에서 기계를 믿을 수 있을까요?

빠진 것: 이 자릿수들은 어떤 미해결 문제에도 답하지 않고, 검증은 방법이 독립적일 때만 하드웨어 오류를 잡아내요.

돌아가는 곳: 약 10¹⁷ FLOPS 대략 수백 조 자릿수를 위해 서버로 몇 달.처음 등장: 1950 라이트비스너가 ENIAC으로 파이와 e를 소수점 아래 2000자리 넘게 구한 것 (1950년 발표, Pi: A Source Book에 재수록). 출처

AI가 이끄는 추측 발견

수학적 대상의 큰 표에 기계 학습을 적용해 어떤 성질들이 서로 연결되는지 찾고, 수학자들이 증명을 시도할 추측을 제안해요.

답하는 질문: 이 수학적 양들 사이의 아직 보이지 않는 어떤 관계가 증명할 만할까?

빠진 것: 패턴을 시사할 뿐 그 자체로는 아무것도 증명하지 못하고, 데이터의 일부 규칙성은 데이터가 만들어진 방식에서 생긴 인공물일 수 있어요.

돌아가는 곳: 약 10¹⁵ FLOPS 대략 데이터세트당 GPU 몇 대로 며칠.처음 등장: 2021 Davies와 동료들의 AI로 사람의 직관을 이끌어 수학을 발전시키기. 출처

학습된 알고리즘과 구성 탐색

게임을 하는 시스템이나 언어 모델 시스템이 새로운 절차나 수학적 대상을 탐색하고, 컴퓨터가 후보마다 올바른지 검증해요.

답하는 질문: 프로그램이 사람들이 찾은 것보다 더 빠른 알고리즘이나 더 큰 예를 발견할 수 있을까요?

빠진 것: 각 결과는 새 예 하나뿐이고, 탐색은 설계자가 게임으로 짠 종류의 대상만 다뤄요.

돌아가는 곳: 약 10¹⁷ FLOPS 대략 가속기 클러스터로 며칠에서 몇 주.처음 등장: 2022 Fawzi와 동료들의 AlphaTensor, 강화 학습으로 더 빠른 행렬 곱셈 알고리즘을 발견함. 출처

모델 검증

프로토콜이나 회로 설계처럼 유한한 시스템의 도달 가능한 모든 상태를 컴퓨터가 나열해, 어떤 성질이 그 모두에서 성립하는지 확인해요.

답하는 질문: 이 설계가 스스로의 규칙을 어기는 도달 가능한 상태가 하나라도 있을까요?

빠진 것: 상태 공간은 검증할 수 있는 범위를 훌쩍 넘어 폭발적으로 커지기 때문에, 실제 설계는 먼저 단순화해요.

돌아가는 곳: 약 10¹² FLOPS 대략 크지만 유한한 상태 공간을 모두 훑는 대학 클러스터처음 등장: 1981 Clarke와 Emerson의 모델 검사 도입

자동 정리 증명 탐색

논리적 추론의 사슬을 컴퓨터가 한 단계씩 만들어 가며 수학적 명제의 증명이나 반증을 찾아요.

답하는 질문: 공리에서 이 명제까지 이어지는 타당한 논리 단계의 사슬이 있을까요?

빠진 것: 사람이라면 고르지 않을 증명을 찾아내고, 손이 닿는 범위에 아예 없을 때도 있어요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 몇 시간에서 며칠 동안 탐색하는 대학 클러스터처음 등장: 1956 논리 이론가(Logic Theorist), 초창기 자동 증명 탐색 프로그램

SAT와 제약 풀이

논리 제약의 큰 집합을 만족하려고 참과 거짓 값의 수백만 가지 조합을 체계적으로 탐색해서, 일정, 경로, 설계 검증에 써요.

답하는 질문: 이 제약들을 모두 한꺼번에 만족하는 값의 배정이 하나라도 있을까요?

빠진 것: 어떤 문제는 아무리 좋은 풀이기를 써도 제때 끝나지 않을 만큼 어려워요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 문제 크기에 따라 워크스테이션에서 클러스터처음 등장: 1962 충족 가능성 탐색을 위한 데이비스-퍼트넘 절차

암호 공격 모델링

암호나 키 교환 방식을 무차별 대입, 통계적 편향, 모델링한 약점으로 시뮬레이션에서 수백만 번 공격해, 실제로 깨는 데 얼마나 노력이 드는지 재요.

답하는 질문: 이것을 깨려면 실제로 연산이 몇 번이나 필요하고, 그 수는 여전히 안전할 만큼 클까요?

빠진 것: 분석가가 모델링할 생각을 한 공격만 시험하고, 아직 아무도 찾지 못한 공격은 시험하지 못해요.

돌아가는 곳: 약 10¹⁴ FLOPS 대략 공격 시도를 돌리는 수많은 기계의 분산 클러스터처음 등장: 1976 1976년까지, 암호와 키 교환 강도의 계산적 분석

부채널 누출 시뮬레이션

기기가 암호 연산을 하는 동안의 소비 전력, 타이밍, 전자기 방출을 모델링해서, 바깥에서 엿듣는 쪽이 거기서 무엇을 알아낼 수 있는지 살펴봐요.

답하는 질문: 비밀 키는 수학이 아니라 장치의 물리적 거동을 통해 얼마나 새어 나올까요?

빠진 것: 실험실 조건은 잡음이 많은 실제 장치가 대개 내주는 것보다 더 깨끗한 신호를 잡아내요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 장치 하나의 전력이나 타이밍 추적을 모델링하는 워크스테이션처음 등장: 1996 코허의 암호 구현에 대한 타이밍 공격 시연

보안 프로토콜 검증

통신 프로토콜에서 공격자가 보내고, 재생하고, 위조할 수 있는 모든 메시지를 컴퓨터가 나열해, 비밀이나 신원을 강제로 빼낼 수 있는지 확인해요.

답하는 질문: 어떤 메시지 열이든 이 프로토콜을 속여 비밀을 흘리게 하거나 가짜 신원을 받아들이게 할 수 있을까요?

빠진 것: 명세에 적힌 대로의 프로토콜을 검증하고, 실제 구현이 택하는 지름길은 검증하지 않아요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 프로토콜 하나의 메시지 공간을 검사하는 워크스테이션에서 클러스터처음 등장: 1989 프로토콜 검증의 기초가 되는 돌레프-야오 모델

전수 사례 검사에 의한 컴퓨터 보조 증명

정리를 유한한 사례 목록으로 줄여 각각을 프로그램으로 검증해요. 사람이 모두 확인할 수 없기 때문이에요.

답하는 질문: 기계가 모든 경우를 확인해 증명을 마칠 수 있을까요?

빠진 것: 신뢰는 프로그램, 하드웨어, 경우 축소 논증으로 옮겨 가요.

돌아가는 곳: 약 10⁹ FLOPS 대략 원본은 메인프레임에서 약 1000시간, 지금은 훨씬 적게.처음 등장: 1977 아펠과 하켄의 모든 평면 지도가 네 가지 색으로 칠해진다는 증명으로, 컴퓨터가 검증한 환원 가능성을 썼어요. 출처

검증된 수치 계산

보장된 한계로 계산을 수행해, 수치 결과가 혼돈 끌개의 존재 같은 수학적 명제를 증명해요.

답하는 질문: 계산한 답이 그저 정확할 가능성이 높은 정도가 아니라, 옳다고 증명될 수 있을까요?

빠진 것: 경계가 오랜 시간에 걸쳐 폭발할 수 있어서, 증명은 짧거나 얌전한 문제로 제한돼요.

돌아가는 곳: 약 10⁹ FLOPS 대략 구간 산술은 비용을 적당한 배수만큼 늘려요.처음 등장: 2002 터커의 엄밀한 상미분 방정식 풀이기와 스메일의 14번째 문제, 로렌츠 끌개가 존재함을 증명. 출처

튜링 기계 열거

최소 기계의 작은 프로그램을 모두 돌려 어떤 것이 멈추고 어떤 것이 영원히 도는지 보고, 크기별로 가장 오래 돌고 멈추는 것을 찾아요.

답하는 질문: 아주 작은 프로그램은 멈추기 전까지 얼마나 오래 돌 수 있을까요?

빠진 것: 결정 불가능성은 어떤 기계는 아무리 오래 돌려도 끝내 분류할 수 없다는 뜻이에요.

돌아가는 곳: 약 10¹⁵ FLOPS 대략 기계 수십억 대, 멈추지 않는 것들은 증명과 함께.처음 등장: 1965 린과 라도의 튜링 기계 문제 컴퓨터 연구 출처

통계적 모델 검증

무작위로 움직이는 시스템을 여러 번 시뮬레이션해, 어떤 성질을 위반할 가능성을 신뢰도와 함께 추정해요.

답하는 질문: 무작위 시스템이 안전 규칙을 깰 가능성은 얼마나 될까요?

빠진 것: 통계적 실행은 증명이 아니라 신뢰 수준이 붙은 확률을 주고, 드문 실패에는 중요도 표집이 필요해요.

돌아가는 곳: 약 10⁹ FLOPS 대략 수천에서 수백만 번의 표집 실행.처음 등장: 2002 유네스와 시먼스의 수용 표집을 이용한 이산 사건 시스템의 확률적 검증이에요. 출처

퍼즈 테스트

프로그램에 무작위이거나 변이한 입력을 엄청나게 많이 넣어 충돌을 일으키는 입력을 찾아요. 말하자면 적대적이거나 부주의한 세계를 시뮬레이션하는 셈이에요.

답하는 질문: 어떤 입력이 이 소프트웨어를 실패하게 만들까?

빠진 것: 무작위 입력이 닿는 실패만 찾아내서, 드문 경우 뒤에 버그가 숨어 있어도 프로그램이 몇 년이나 무사히 통과할 수 있어요.

돌아가는 곳: 약 10¹⁴ FLOPS 대략 대규모 코드베이스 하나에 CPU 시간으로 기계-년.처음 등장: 1990 Miller, Fredriksen and So's empirical study of the reliability of UNIX utilities. 출처

기호 실행

프로그램을 모르는 입력을 기호로 쓴 채 돌리며 각 경로의 조건을 모은 다음, 풀이기가 각 분기를 타게 하는 값을 찾아요.

답하는 질문: 어떤 입력이 이 프로그램의 각 경로를 실행시키고, 그중 버그에 닿는 것이 있을까?

빠진 것: 경로의 수는 프로그램 크기에 따라 기하급수적으로 늘어서, 큰 프로그램은 일부만 다룰 수 있어요.

돌아가는 곳: 약 10¹² FLOPS 대략 프로그램당 풀이 시간 몇 시간, 경로 수에 따라 가파르게 늘어요.처음 등장: 1976 King's symbolic execution and program testing. 출처

추상 해석

프로그램을 단일 값 대신 범위 같은 가능한 값의 집합으로 돌려, 모든 입력에서 성립하는 성질을 증명해요.

답하는 질문: 이 프로그램이 어떤 입력에서든 0으로 나누거나 넘칠 수 있을까요?

빠진 것: 안전한 근사는 오경보를 늘려서, 사람이 여전히 경고마다 확인해야 해요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 대규모 항공 전자 코드베이스를 위한 워크스테이션 몇 시간.처음 등장: 1977 Cousot와 Cousot의 추상 해석, 프로그램 정적 분석을 위한 통합된 격자 모델. 출처

한정 모델 검사

설계의 동작을 정해진 단계 수까지 논리식으로 적어 충족 가능성 풀이기에 넘기면, 버그로 가는 짧은 경로를 아무거나 찾아 줘요.

답하는 질문: 이 회로나 프로그램이 주어진 단계 수 안에 오류 상태에 이를 수 있을까요?

빠진 것: 별도의 논증으로 충분하다는 것을 보이지 않는 한, 단계 한계 너머로는 아무것도 증명하지 못해요.

돌아가는 곳: 약 10¹³ FLOPS 대략 속성 하나당 서버로 몇 시간.처음 등장: 1999 비에레, 치마티, 클라크, 주의 BDD 없는 기호 모델 검사. 출처

속성 기반 무작위 시험

항상 성립해야 하는 규칙을 적어 두면, 컴퓨터가 무작위 사례를 많이 만들고 실패를 작은 반례로 줄여 줘요.

답하는 질문: 이 코드가 폭넓은 입력에서 자신의 명세를 지킬까요?

빠진 것: 무작위 사례는 드문 조건에 끝내 도달하지 못할 수 있고, 적어 둔 성질이 중요한 성질이 아닐 수 있어요.

돌아가는 곳: 약 10⁹ FLOPS 대략 노트북으로 수천 건에 몇 분.처음 등장: 2000 Claessen과 Hughes의 QuickCheck, Haskell 프로그램의 무작위 시험을 위한 가벼운 도구. 출처

신경망 검증

제약 풀이기가 한 영역의 모든 입력에 대해 신경망의 출력이 한계 안에 머문다는 것을, 표본을 시험하는 대신 증명해요.

답하는 질문: 입력을 조금만 바꿔도 신경망이 틀린 답을 낼 수 있을까요?

빠진 것: 증명은 작은 네트워크에만 확장되고, 확인할 수 있는 섭동의 집합은 좁아요.

돌아가는 곳: 약 10¹³ FLOPS 대략 작은 네트워크 하나를 위한 서버 몇 시간에서 며칠.처음 등장: 2017 Katz와 동료들의 Reluplex, 심층 신경망을 검증하는 SMT 풀이기 출처

컴퓨터 아키텍처 시뮬레이션

제안된 프로세서의 파이프라인, 캐시, 분기 예측기를 명령어 단위로 모델링해, 칩을 만들기 전에 속도를 추정해요.

답하는 질문: 이 프로세서 설계는 실리콘을 깎기 전에 실제 프로그램을 얼마나 빠르게 돌릴까요?

빠진 것: 실제 칩의 많은 부분을 단순화해서, 최종 실리콘은 늘 모델과 조금 달라요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 벤치마크 프로그램을 모델에 돌리는 대학 클러스터처음 등장: 1990 1990년까지, 아키텍처 연구를 위한 사이클 정확 프로세서 시뮬레이터

분산 시스템과 합의 시뮬레이션

많은 컴퓨터가 지연, 유실, 고장이 있는 가운데 서로 메시지를 보내는 상황을 모델링해서, 분산 알고리즘이 여전히 옳은 답에 합의하는지 시험해요.

답하는 질문: 메시지가 유실되거나 늦어지거나 노드가 멈춰도 이 알고리즘이 올바른 합의에 도달할까요?

빠진 것: 주입되는 고장은 설계자가 예상한 것이지, 운영 중에 뜻밖에 생기는 것이 아니에요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 가상 노드 수백 개를 시뮬레이션하는 클러스터처음 등장: 1978 래포트의 분산 시스템에서의 순서와 실패에 관한 초기 연구

저장 시스템 시뮬레이션

디스크, 드라이브, 파일 시스템을 데이터 배치, 고장, 복구 방식으로 모델링해, 실제 드라이브를 사서 채우기 전에 저장 설계를 시험해요.

답하는 질문: 이 저장 장치 설계는 먼저 실제로 시험하기엔 비용이 너무 큰 규모에서 어떻게 성능을 내고 고장을 견딜까요?

빠진 것: 실제 드라이브는 모델의 무작위 고장률보다 더 지저분하고 상관관계가 있는 방식으로 고장 나요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 저장 장치 배열을 모델링하는 워크스테이션에서 소형 클러스터처음 등장: 1988 1988년까지, 디스크 배열 신뢰성 시뮬레이션 모델

운영 체제 스케줄러 시뮬레이션

컴퓨팅 작업의 흐름이 도착해 프로세서를 두고 다투는 상황을 모델링하고, 여러 스케줄링 규칙으로 돌려 어느 쪽이 가장 공정하거나 빠른지 봐요.

답하는 질문: 작업 대기열을 어떤 순서로 정하면 가장 많은 일을 해내거나, 모든 작업에 가장 공평할까?

빠진 것: 합성 작업 부하는 실제 기계가 맞닥뜨리는 불규칙한 작업의 조합과 좀처럼 맞지 않아요.

돌아가는 곳: 약 10⁹ FLOPS 대략 노트북이나 워크스테이션에서 몇 초에서 몇 분이면 돌아가요처음 등장: 1968 1968년까지, 프로세서 스케줄링 정책 시뮬레이션 연구

컴파일러와 프로그램 최적화 탐색

코드 한 조각의 작은 변형을 엄청나게 많이 시도하고 재서, 같은 일을 하는 가장 빠르거나 가장 짧은 버전을 찾아요.

답하는 질문: 이 작은 코드를 쓰는 모든 동등한 방법 가운데 실제로 가장 빠른 것은 무엇일까요?

빠진 것: 발견된 프로그램은 때로 너무 특이해서 왜 작동하는지에 대한 설명이 없어요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 방대한 코드 변형 공간을 탐색하는 클러스터처음 등장: 2006 2006년까지, 짧은 명령어 열에 대한 슈퍼 최적화 탐색

알고리즘 성능 실증 시험

알고리즘을 점점 커지는 무작위 또는 실제 입력에 수천 번 돌려, 종이 위에서 증명하는 대신 실행 시간이 실제로 어떻게 늘어나는지 재요.

답하는 질문: 이 알고리즘의 실행 시간은 실제로 마주칠 입력에서 현실적으로 어떻게 늘어날까요?

빠진 것: 테스트 입력에 없는 최악의 경우는 실제로 일어날 때까지 발견되지 않아요.

돌아가는 곳: 약 10⁹ FLOPS 대략 워크스테이션에서 생성한 많은 시험 입력에 걸쳐 돌아가요처음 등장: 1970 1970년까지, 알고리즘 실행 시간에 대한 체계적인 실증 시험

언어 모델 프로그램 실행

언어 모델이 프로그램이 계산할 중간 상태를 따라가며 단계별로 적어 내려가요.

답하는 질문: 언어 모델이 코드 실행을 에뮬레이션할 수 있을까요?

빠진 것: 출력이 맞다는 보장이 없고, 긴 프로그램은 실패해요.

돌아가는 곳: 약 10¹⁴ FLOPS 대략 질의당 추론처음 등장: 2021 Show your work: scratchpads for intermediate computation with language models (2021) 출처

블록체인 합의 시뮬레이션

노드 네트워크가 지연 속에서 블록을 만들고 나눠, 블록 크기, 타이밍, 공격자가 보안과 처리량에 어떤 영향을 주는지 시험해요.

답하는 질문: 블록체인은 네트워크 지연과 공격 속에서 얼마나 안전하고 빠를까요?

빠진 것: 실제 노드의 행동과 네트워크 구조는 일부만 측정돼요.

돌아가는 곳: 약 10⁸ FLOPS 대략 노드 수천 개의 사건 구동 실행.처음 등장: 2016 Gervais와 동료들의 시뮬레이터를 이용한 작업 증명 블록체인의 보안과 성능 분석. 출처

병렬 이산 사건 시뮬레이션

시간 속 사건의 시뮬레이션을 여러 프로세서에 나눠, 각자 자기 시계를 진행시키다 하나가 늦게 도착하면 되돌려요.

답하는 질문: 네트워크나 전장처럼 거대한 사건 구동형 시뮬레이션을 여러 기계에서 어떻게 빠르게 돌릴 수 있을까요?

빠진 것: 롤백이 연쇄적으로 일어날 수 있고, 속도 향상은 사건들이 얼마나 단단히 묶여 있느냐에 크게 좌우돼요.

돌아가는 곳: 약 10¹⁴ FLOPS 대략 수십억 건의 이벤트를 위한 슈퍼컴퓨터 몇 시간.처음 등장: 1985 제퍼슨의 가상 시간, 낙관적 동기화를 위한 타임 워프 메커니즘 출처

그래픽 프로세서 아키텍처 시뮬레이션

그래픽 처리 장치의 코어, 워프, 메모리를 사이클 단위로 모델링하고 실제 프로그램을 돌려, 만들기 전에 설계를 평가해요.

답하는 질문: 설계를 바꾸면 그래픽 칩에서 병렬 프로그램의 속도에 어떤 영향이 있을까요?

빠진 것: 실제 칩의 세부는 비밀이거나 알려지지 않아서, 모델은 기존 설계의 수치와 대략만 맞아요.

돌아가는 곳: 약 10¹² FLOPS 대략 시뮬레이션된 실행 1초당 호스트로 몇 시간에서 며칠.처음 등장: 2009 바코다와 동료들의 상세 GPU 시뮬레이터를 이용한 CUDA 작업 부하 분석. 출처

FPGA 가속 시스템 시뮬레이션

칩 설계를 재구성 가능한 회로 여러 개에 올려 메가헤르츠 속도로 사이클 단위까지 정확하게 돌리며, 서버 전체와 그 네트워크를 시뮬레이션해요.

답하는 질문: 이 프로세서와 클러스터는 만들어지기 전에 실제 소프트웨어를 돌리면 어떻게 동작할까요?

빠진 것: 실제 칩보다 훨씬 느리고, 회로에 맞지 않는 설계는 돌릴 수 없어요.

돌아가는 곳: 약 10¹⁵ FLOPS 대략 수백 개의 재구성 가능한 회로 클라우드에서 며칠.처음 등장: 2018 Karandikar와 동료들의 FireSim, 공개 클라우드에서 FPGA로 가속한 사이클 정확 스케일 아웃 시스템 시뮬레이션 출처

전체 시스템 시뮬레이션

프로세서, 메모리, 디스크, 네트워크 카드까지 갖춘 컴퓨터 한 대를 통째로, 수정하지 않은 운영 체제가 부팅하고 그 프로그램이 돌아갈 만큼 잘 시뮬레이션해요.

답하는 질문: 아직 존재하지 않거나 마음대로 멈추고 되돌릴 수 있는 기계에서 실제 소프트웨어는 어떻게 동작할까요?

빠진 것: 속도를 위해 타이밍은 근사해서, 정확한 성능은 알 수 없고 기능적 동작만 알 수 있어요.

돌아가는 곳: 약 10¹¹ FLOPS 대략 시뮬레이션된 기계 한 대당 서버로 거의 실시간.처음 등장: 2002 Magnusson과 동료들의 Simics, 전체 시스템 시뮬레이션 플랫폼 출처

경량 네트워크 에뮬레이션

가상 호스트와 스위치 수십에서 수백 개가 노트북 한 대에서 실제 네트워크 소프트웨어를 돌리며, 속도와 지연이 정해진 에뮬레이션 케이블로 이어져요.

답하는 질문: 이 네트워크 제어 프로그램은 배포하기 전에 전체 토폴로지에서 제대로 동작할까?

빠진 것: 호스트의 프로세서를 모든 가상 노드가 함께 쓰기 때문에, 빠른 링크가 느려져요.

돌아가는 곳: 약 10¹⁰ FLOPS 대략 워크스테이션 한 대에서 실시간.처음 등장: 2010 Lantz, Heller and McKeown's 'A network in a laptop', rapid prototyping for software-defined networks. 출처

시뮬레이티드 어닐링

컴퓨터가 원자나 설계의 모델을 천천히 식히면서 가끔 더 나쁜 배열도 받아들여, 어려운 최적화 문제의 좋은 해를 찾아요.

답하는 질문: 천문학적으로 많은 가능성 가운데 최선에 가까운 배치나 일정은 무엇일까?

빠진 것: 최선의 답이라는 보장이 없고, 결과는 냉각 일정에 따라 달라져요.

돌아가는 곳: 약 10¹² FLOPS 대략 칩 배치 하나에 워크스테이션으로 몇 시간.처음 등장: 1983 Kirkpatrick, Gelatt and Vecchi's optimisation by simulated annealing. 출처

근사 베이즈 계산

시뮬레이터를 여러 시험 매개변수 값으로 돌려, 관측 데이터와 가까운 데이터를 내는 값만 남겨 어떤 값이 그럴듯한지 그림을 얻어요.

답하는 질문: 복잡한 모델의 어떤 설정이 우리가 관측한 자료를 만들어 낼 수 있었을까?

빠진 것: 결과는 자료의 어떤 요약을 쓰느냐와, 얼마나 가까워야 일치로 치느냐에 달려 있어요.

돌아가는 곳: 약 10¹³ FLOPS 대략 클러스터에서 수백만 번의 시뮬레이터 실행.처음 등장: 1997 타바레와 동료들이 시뮬레이션으로 DNA 서열 자료에서 합체 시간을 추론한 연구예요. 출처