Networked Physics - Game Networking
Networked Physics by Glenn Fiedler을 정리한 글입니다.
Glenn Fiedler 는 Network Next 의 설립자이자 CEO입니다 . Network Next 는 프리미엄 네트워크 전송을위한 마켓 플레이스를 만들어 게임용 인터넷을 수정하고 있습니다.
Game Networking
Floating Point Determinism
Glenn Fiedler 는 2010년 2월에 Deterministic lockstep 방식을 사용한 네트워킹 게임 물리 시뮬레이션에 대해 연구하고 있었습니다.
기본적인 아이디어는 시뮬레이션의 동기화를 물리적인 객체의 위치, 방향, 속도를 직접 전송하여 상태를 동기화하지 않고,
네트워크를 통해 플레이어의 입력만 전송하여 암시적으로 동기화하는 것입니다.
이는 네트워크 트래픽량이 시뮬레이션의 물리 상태 데이터량 대신 플레이어 입력의 크기에 따라 달라지기 때문에 매우 매력적인 동기화 전략입니다. 사실, 이 전략은 이러한 이유로 RTS 게임에서 수 년 동안 사용되어 왔습니다; 수천 개의 유닛이 지도에 나와 있는 상황에서, 네트워크를 통해 전송할 상태가 너무 많았습니다.
아마도 강체 상태(Rigid Body State)가 많은 복잡한 물리 시뮬레이션이나 두 기계 간 완벽한 동기화를 해야하는 천이나 연체 시뮬레이션이 필요하지만, 모든 상태를 보낼 여유가 없을 수 있습니다
이 상황에서 가능한 유일한 해결책은 결정론적(Deterministic) 네트워킹 전략을 시도하는 것입니다.
그러나 곧 문제에 부딪히게 됩니다. 물리 시뮬레이션은 부동소수점 계산을 사용하며,
여러 이유로 두 개의 서로 다른 기기에서 부동소수점 계산으로 정확히 같은 결과를 얻는 것은 매우 어려운 작업입니다.
심지어 같은 기기에서 실행될때마다 또는 디버그 빌드와 릴리스 빌드 사이에서도 다른 결과가 나올 수 있습니다.
다른 사람들은 AMDs가 인텔 기기에 다른 결과를 제공하며 SSE 결과는 x87과 다르다고 말합니다.
정확히 무슨 일일까요? 부동소수점 계산은 결정론적인가요 아닌가요?
안타깝게도 대답은 단순한 예 나 아니오 가 아니라, 예, 만약… 입니다.
지금까지 Glenn 이 발견한 것은 다음과 같습니다:
- 물리 시뮬레이션 자체가 결정적이라면 약간의 작업을 통해 동일한 머신에서 기록된 입력을 재생하여 정확히 동일한 결과를 얻을 수 있어야 합니다.
- 동일한 컴파일러로 구축된 실행 파일을 사용하고, 동일한 아키텍처의 시스템에서 실행되며, 플랫폼별 몇 가지 기술을 수행한다면 여러 컴퓨터에서 부동소수점 계산에 대한 결정론적 결과를 얻을 수 있습니다.
- C 또는 C ++로 임의의 부동소수점 코드를 작성하고 서로 다른 컴파일러 또는 아키텍처에서 정확히 동일한 결과를 얻거나
디버그 및 릴리스 빌드에서 동일한 결과를 얻을 것으로 기대하는 것은 매우 순진한 생각입니다. - 그러나 많은 작업을 수행하면 가능할 수 있습니다. 컴파일러의 “엄격한”(strict) IEEE 754 호환 모드를 사용하고 사용하는 부동소수점 작동을 제한함으로써 서로 다른 컴파일러 또는 다른 아키텍처에서 정확히 동일한 부동소수점 결과를 유도할 수 있습니다.
하지만 이것은 일반적으로 부동소수점 성능을 현저히 낮춥니다.
지금까지 Glenn이 찾은 리소스는 다음과 같습니다:
다양한 고객에게 라이선스를 제공하는 우리 기술은 부동소수점(64 비트 모드에서도) 결정론을 기반으로 하며
2000 년부터 그렇게 작동했습니다.
단일 컴파일러와 단일 CPU 명령어 세트를 고수하는 한 부동소수점을 완전히 결정론적으로 만들 수 있습니다.
세부 사항은 플랫폼에 따라 다릅니다(예: x86, x64 및 PPC가 다름).내부 정밀도가 64 비트(인텔 만 구현하므로 80이 아님)로 설정되어 있고 반올림 모드가 일관성이 있는 지 확인해야 합니다.
또한 많은 DLL(Direct3D, 프린터 드라이버, 사운드 라이브러리 등)이 다시 설정하지 않고
정밀도 또는 반올림 모드를 변경하므로 외부 DLL을 호출한 후에 이를 확인해야 합니다.ISA는 IEEE 규격입니다. x87 구현이 IEEE가 아니면 x87이 아닙니다.
또한 SSE 또는 SSE2를 부동소수점으로 사용할 수 없습니다. 결정적 이기에는 너무 과소(under-specified)하기 때문입니다.
저는 Gas Powered Games에서 일하고 있으며 부동소수점 수학이 결정 론적이라고 직접 말할 수 있습니다.
동일한 명령어 세트와 컴파일러 만 있으면됩니다.
물론 사용자의 프로세서는 모든 PC 및 360 고객을 포함하는 IEEE754 표준을 준수합니다.
DemiGod, Supreme Commander 1 및 2를 실행하는 엔진은 IEEE754 표준을 따릅니다.
…
리플레이를 컨트롤러 입력으로 저장하면 CPU 아키텍처, 컴파일러 또는 최적화 설정이 다른 머신에서 재생할 수 없습니다.
MotoGP에서 이것은 Xbox와 PC간에 저장된 리플레이를 공유할 수 없다는 의미입니다.
또한 게임의 디버그 빌드에서 리플레이를 저장하면 릴리스 빌드에서 작동하지 않거나 그 반대의 경우도 마찬가지입니다.
이것은 항상 문제가되는 것은 아니지만(결국 디버그 빌드를 제공 한 적이 없습니다), 패치를 출시 한 적이 있다면
원래 게임과 똑같은 컴파일러를 사용하여 빌드해야 했습니다.
컴파일러가 원래 릴리스 이후로 업데이트되었고 최신 컴파일러를 사용하여 패치를 빌드했다면
원래 게임에서 저장한 리플레이가 더 이상 제대로 재생되지 않을 정도로 상황이 바뀔 수 있습니다.
이것은 미친 짓입니다! 모든 하드웨어가 동일하게 작동하도록 하지 않는 이유는 무엇입니까?
음, 우리가 성능에 관심이 없다면 할 수 있습니다. “이봐, 하드웨어 친구, 미친 융합 곱셈 명령은 잊어 버리고
기본적인 IEEE 구현 만 해주세요”, “컴파일러 친구, 코드 최적화에 신경 쓰지 마세요”라고 말할 수 있지만,
그렇게하면 우리 프로그램이 모든 곳에서 일관되게 느리게 실행됩니다. :-)
Battlezone 2는 모든 클라이언트에서 중요하지 않은 부분까지 완전히 결과를 요구하는 락스텝 네트워킹 모델을 사용했습니다.
그렇지 않으면 시뮬레이션이 발산될 것입니다.
이것을 달성하기 어려웠지만, 그것은 네트워크를 통해 사용자 입력을 보내기만 하면 된다는 의미입니다;
다른 모든 게임 상태는 로컬에서 계산될 수 있습니다.
개발 과정에서 AMD와 Intel 프로세서가 초월적 함수(sin, cos, tan 및 그 역함수)에 대해
약간 다른 결과를 생성한다는 사실을 발견했기 때문에 컴파일러가 단정밀(Single-precision)으로 남겨두도록 강제하기 위해
최적화되지 않은 함수 호출로 포장해야했습니다.
AMD와 Intel 프로세서를 일관되게 만들었지만, 확실히 학습 경험이었습니다.
… FSW1에서 플레이어에게 비동기화(desync)가 감지되면 “매직 스나이퍼”에 의해 즉시 죽습니다.
:) 그 모든 것들은 FSW2에서 수정되었습니다.
정확한 FP를 실행하고 PC에서 SIMD 대신 Havok FPU 라이브러리를 사용했습니다.
또 정수 모듈로도 문제가 되는 것은 C ++ 표준이 “구현 정의”(여러 컴파일러 / 플랫폼이 사용되는 경우)라고
명시하고 있기 때문입니다.
일반적으로 우리가 개발한 락 스텝을 위한 도구로 FSW2의 코드에서 비동기화를 쉽게 찾을 수 있었습니다.
Branimir Karadžić, Pandemic Studios
저는 부동소수점 불일치 문제의 세 가지 주요 원인을 알고 있습니다.
대수(Algebraic) 컴파일러는 다른 플랫폼에서는 사용할 수 없는 곱셈 누적이나 x86의 sine 문제와 같은
“복잡한” 명령을 최적화합니다;
내장되지 않은 장치들이 문제를 공유하고 있다는 것은 아닙니다.좋은 소식은 대부분의 문제가 자동으로 해결될 수있는 항목3 에서 비롯된다는 것입니다.
의사 결정의 목적(“FP 일관성에 에너지를 투자해야합니까, 아니면 헛된 것입니까?”)을 위해,
헛되지 않고 일관성에서 얻을 수있는 실제 이점을 인용할 수 있다면, (지속적인)노력의 가치가 있다고 말하고 싶습니다.요약: SSE2 또는 SSE를 사용하고, 사용할 수 없는 경우 64b 중간자(intermediates)를 사용하고
32b Float를 피하도록 FP CSR을 구성하십시오.
후자의 솔루션조차도 모든 사람이 알고있는 한 실제로 무난하게 작동합니다.
짧은 대답은 FP 계산이 IEEE 부동소수점 표준에 따라 전적으로 결정적이라는 것입니다.
그러나 그렇다고 해서 시스템, 컴파일러, OS 등에서 완전히 재현할 수 있다는 의미는 아닙니다.
이러한 질문에 대한 좋은 답변은 부동소수점에 대한 가장 좋은 참고자료인 David Goldberg 의 모든 컴퓨터 과학자가 부동소수점 연산에 대해 알아야 할 사항에서 찾을 수 있습니다.
주요 세부 사항은 IEEE 표준 섹션을 참고하세요마지막으로, 동일한 초기 입력에 대해 동일한 순서의 부동소수점 계산을 수행하는 경우
모든 것이 정확하게 재생 가능해야 합니다.
정확한 순서는 컴파일러/OS/표준 라이브러리에 따라 바뀔 수 있기 때문에, 약간의 오류가 발생할 수 있습니다.일반적으로 부동소수점에서 문제가 발생하는 곳은 수치적으로 불안정한 방법을 사용하고, FP 입력이 거의 동일하지만 정확하지 않은 경우입니다.
방법이 안정적인 경우 일부 허용 오차 내에서 재현성을 보장할 수 있습니다.
이보다 더 자세한 정보를 원하시면 위에 링크 된 Goldberg의 FP 기사를 보거나 수치 분석에 대한 소개 글을 선택하세요.
C ++ 표준은 부동소수점 타입 float, double 및 long double에 대한 이진 표현을 지정하지 않습니다.
표준에서는 필요하지 않지만 대부분의 C ++ 컴파일러에서 사용하는 부동소수점 산술 구현은
ㄴ최소한 float 및 double 유형에 대해 표준 IEEE 754-1985를 준수합니다.
이는 최신 CPU의 부동소수점 단위도 이 표준을 지원한다는 사실과 직접적으로 관련이 있습니다.
IEEE 754 표준은 부동소수점 숫자에 대한 이진 형식과 부동소수점 연산의 의미를 지정합니다.
그럼에도 불구하고 다양한 컴파일러가 IEEE 754의 모든 기능을 구현하는 정도는 다양합니다.
이것은 C++로 이식 가능한 부동소수점 코드를 작성하는 모든 사람에게 다양한 함정을 만듭니다.
Günter Obiltschnig, Cross-Platform Issues with Floating-Point arithmetics in C++
부동소수점 연산은 FPU 하드웨어 구현, 컴파일러 및 최적화, 시스템 수학 라이브러리(libm)에 크게 의존합니다.
실험은 일반적으로 동일한 시스템 라이브러리와 동일한 옵션을 사용하는 동일한 컴파일러가 있는 동일한 컴퓨터에서만
재현 할 수 있습니다.
부동소수점(FP) 프로그래밍 목표: • 정확성 - 정확한 값에 “가까운” 결과 생성
• 재현성 - 한 실행에서 다음 실행까지 일관된 결과를 생성합니다.
한 세트의 빌드 옵션에서 다른 세트로.
한 컴파일러에서 다른 컴파일러로.
한 플랫폼에서 다른 플랫폼으로.
• 성능 – 가능한 가장 효율적인 코드를 생성합니다.이러한 옵션은 일반적으로 충돌합니다! 컴파일러 옵션을 적절하게 사용하면 장단점을 제어할 수 있습니다.
Intel C++ Compiler: Floating Point Consistency
엄격한 재현성과 일관성이 중요한 경우
fp-model strict (Linux 또는 Mac OS ) 또는 */fp:strict (Windows ) 옵션 또는
*pragma fenv_access 를 사용하지 않고 부동 소수점 환경을 변경하지 마십시오.
fp:strict 모드에서 컴파일러는 부동 소수점 계산의 정확도를 방해하는 최적화를 수행하지 않습니다.
컴파일러는 할당, 형변환 및 함수 호출에서 항상 올바르게 반올림되며 중간 반올림은 FPU 레지스터와 동일한
정밀도로 일관되게 수행됩니다.
부동 소수점 예외 의미 체계 및 FPU 환경 민감도는 기본적으로 활성화되어 있습니다.
컴파일러가 모든 경우에 정확성을 보장할 수 없기 때문에 축소(contractions)와 같은 최적화는 비활성화됩니다.
Microsoft Visual C++ Floating-Point Optimization
PowerPC 스칼라 및 벡터 FPU 코어는 FMA(Fused Multiply-Add) 연산을 중심으로 설계 되었기 때문에
부동 소수점 계산의 결과는 PowerPC 와 Intel 간에 정확히 동일하지 않을 수 있습니다.
Intel 칩에는 별도의 Multiplier 와 가산기(Adder)가 있으므로 이러한 작업을 별도로 수행해야 합니다.
즉, 계산의 일부 단계에서 Intel CPU는 추가 반올림 단계를 발생시켜 계산의 곱셈 단계에서 1/2 ulp 오류를 유발할 수 있습니다.
Note:
Fused Multiply-Add(FMA) 는 단일 곱셈-누산으로 부동소수점 곱하기와 더하기를 한번에 수행합니다.
즉 두 수를 곱한 값을 누산기에서 또 다른 값과 더하는 동작입니다.
IEEE 연산인 모든 명령어(, +, -, /, sqrt, compare, SSE와 x87과 관계없이)에 대해,
동일한 제어 설정(동일한 정밀 제어 및 반올림 모드, 0으로 플러시 등)과 입력을 가진 플랫폼 전체에 걸쳐
동일한 결과를 산출합니다. 이것은 32 비트 및 64 비트 프로세서 모두에 해당됩니다.
x87 측면에서 *fsin, fcos 등과 같은 초월적인 명령어는 구현에 따라 약간 다른 답변을 할 수 있습니다.
이는 보장되는 상대적인 오류지만 비트 단위로 정확하지 않습니다.
Intel Software Network Support
IEEE-754의 하드웨어 구현 간에 가능한 차이점이 우려됩니다.
저는 이미 소스 코드와 어셈블리 수준의 실제 실행 사이에 미묘한 차이가 발생하는
프로그래밍 언어의 문제에 대해 알고 있습니다.
[Mon08] 지금은 개별 지침 수준에서 Intel/SSE 와 PowerPC 의 차이점에 관심이 있습니다.
D. Monniaux on IEEE 754 mailing list
한 구현에서 다른 구현으로 올바로 반올림하지 않거나 심지어 일관되게 반올림하지 않는
역(inverse) 및 역 sqrt 뿐만 아니라, AMD와 Intel 에서 다르게 구현되는 x87 초월 연산과 같은
비 754 명령어를 피해야합니다.
David Hough on 754 IEEE mailing list
예, 재현 가능한 결과를 얻을 수 있습니다.
그러나 해당 속성을 제공하기 위한 프로그래밍 방법론을 정의하지 않고서는 이를 수행할 수 없습니다.
그리고 그것은 지지자들이 인정하는 것보다 훨씬 더 과감한 결과를 가져옵니다.
특히 대부분의 병렬 처리와 효과적으로 호환되지 않습니다.
Nick Maclaren on 754 IEEE mailing list
IEEE 754-1985는 구현에서 많은 변형을 허용했습니다(예를 들면,
일부 값의 인코딩 및 특정 예외 감지).
IEEE 754-2008은 이들 중 많은 부분을 강화했지만 여전히 몇 가지 변형이 남아 있습니다(특히 바이너리 형식의 경우).
재현성 조항은 언어 표준이 재현 가능한 프로그램을 작성하는 수단(즉, 언어의 모든 구현에서 동일한 결과를 생성하는
프로그램)을 제공해야 한다고 권고하지만, 재현 가능한 결과를 얻기 위해 해야 할 작업을 설명합니다.
Wikipedia Page on IEEE 754-2008 standard
댓글남기기