이 비디오에서 Alan Edelman은 기계 학습을 위한 프로그래밍 언어의 힘과 수학에서의 중요성에 대해 설명합니다. 그는 기술적 장점과 기계 학습에서의 유용성으로 인해 Google에서 인정한 Julia 언어의 최근 개발을 강조합니다. Edelman은 Julia의 자동 미분 작동 방식을 설명하고 Babylonian 알고리즘을 통해 수치적 유한 차이를 사용하지 않고 x의 제곱근을 계산하는 예를 제공합니다. 또한 효율적인 계산을 위해 Julia에서 유형을 사용하고 블록 행렬을 사용하여 역전파 프로세스를 단순화하는 방법에 대해서도 설명합니다. 전반적으로 Edelman은 수학적 계산을 위한 선형 대수학의 중요성과 복잡한 현상을 이해하는 역할을 강조합니다.
00:00:00 이 섹션에서 Alan Edelman은 행 순위가 열 순위와 같다는 Strang 교수의 시연과 이 개념이 제로 행렬에 어떻게 적용되는지 설명합니다. 그런 다음 머신 러닝에서 인기를 얻고 있는 프로그래밍 언어인 Julia의 최근 개발과 Google이 이 분야에서 그 힘을 어떻게 인정했는지에 대해 이야기합니다. Google은 최근 기계 학습에 충분히 강력한 언어는 두 가지뿐이며 Julia는 그 중 하나라는 블로그 게시물을 게시했습니다. Edelman은 이 점을 설명하는 예를 제공하고 학생들이 자세한 내용은 블로그 게시물을 확인하도록 권장합니다.
00:05:00 이 섹션에서 Alan Edelman은 수학적 의미에서 프로그래밍 언어의 중요성과 단순한 알고리즘 구현 이상의 기능에 대해 설명합니다. 그는 줄리아, 스위프트, C++, 러스트가 기술적 장점과 유용성을 기반으로 기계 학습에 적합하다고 판단되는 4가지 프로그래밍 언어라고 설명합니다. Edelman은 모든 공학 과정의 기초로서 선형 대수학의 중요성과 불행한 역사 지연을 강조합니다. 그런 다음 그는 자동 미분과 그것이 미적분과 어떻게 관련되는지, 그것에 대한 그의 초기 회의론, 순방향 모드 자동 미분에 대한 노트북에서 탐구한 기술적 세부 사항을 탐구합니다.
00:10:00 이 섹션에서 Alan Edelman은 자동 미분에 대한 초기 생각과 그것이 학교에서 컴퓨터로 배운 미적분과 같다고 생각한 방법에 대해 설명합니다. 그러나 그는 곧 유한차이도 연쇄법칙도 아닌 세 번째 방법이 있음을 깨닫고 매료되었습니다. 그런 다음 그는 Julia에서 Babylonian 알고리즘을 사용하여 x의 제곱근을 계산한 방법과 Julia의 자동 미분 기능 덕분에 미분 공식을 명시적으로 입력하지 않고도 제곱근의 미분을 얻을 수 있었던 방법에 대한 예를 공유합니다.
00:15:00 이 섹션에서 화자는 Julia 코드를 사용하여 유한 차분 계산을 사용하지 않고 숫자의 제곱근을 계산하는 방법을 설명합니다. 이 코드는 수치 함수와 그 도함수를 나타내는 부동 소수점 쌍인 "이중 숫자"라는 변수 유형을 생성합니다. 그런 다음 화자는 더하기 및 나누기 연산을 오버로드하여 몫 규칙을 구현하여 Babylonian 알고리즘을 사용하여 제곱근을 계산할 수 있습니다. 이 코드는 수치적 유한 차이를 사용하지 않고 작동하며 화자는 Julia가 "마법"을 수행하기 위해 새로운 컨텍스트에서 기존 코드를 재사용할 수 있도록 허용한다고 말합니다.
00:20:00 이 섹션에서 Alan Edelman은 Julia 프로그래밍 언어가 어셈블러 코드의 이중 숫자에서 Babylonian 알고리즘을 사용하여 도함수를 효율적으로 계산하는 방법을 설명합니다. 그는 Python의 기호 계산 패키지에서 실행되는 동일한 코드가 매우 비효율적인 큰 계수로 기호 계산을 제공하는 방법을 보여줍니다. 그런 다음 그는 Babylonian 알고리즘이 작동하는 방식을 확신시킨 또 다른 알고리즘인 SVD를 공개합니다. 코드의 모든 라인에서 도함수를 취함으로써 알고리즘은 제곱근과 제곱근의 도함수로 수렴할 수 있습니다. 결과 도함수는 기호나 숫자가 아니라 답을 얻기 위해 모든 단계에서 몫 규칙과 덧셈 규칙을 사용합니다.
00:25:00 이 섹션에서는 Julia 언어의 창시자인 Alan Edelman이 언어에서 자동 미분이 어떻게 작동하는지 설명합니다. Edelman은 각 라인의 파생물을 수동으로 가져오는 대신 JIT 컴파일러가 처리하도록 함으로써 소프트웨어가 이를 자동으로 수행할 수 있다고 제안합니다. 이렇게 하면 번역가나 손글씨를 작성할 필요가 없어 코딩이 훨씬 간소화됩니다. Edelman은 머신 러닝이 최적화 문제에 크게 의존하며, 이 문제는 모두 미분을 취하는 것과 관련되어 자동 미분을 프로세스의 필수 구성 요소로 만드는 것이라고 말합니다. 마지막으로 그는 유형을 사용하여 데이터를 저장하는 구조화된 행렬 생성을 단순화하는 방법을 설명합니다.
00:30:00 이 섹션에서 Alan Edelman은 계산을 수행할 때 필요한 항목만 효율적으로 저장하기 위해 Julia에서 유형을 사용하는 방법에 대해 설명합니다. 이는 오버헤드가 더 많은 Python 및 MATLAB과 같은 언어와 차별화됩니다. 그런 다음 그는 스칼라 예제로 시작하여 행렬과 벡터로 일반화하여 신경망의 몰입 모드 차별화 아이디어에 대해 간략하게 설명합니다. 그는 이 과정과 관련된 선형 대수를 작성하지만 완전히 설명하기 전에 시간이 부족합니다.
00:35:00 이 섹션에서 Edelman은 Julia에서 블록 행렬을 사용하여 도함수를 수동으로 계산할 필요 없이 역전파를 수행하는 방법을 설명합니다. 그는 대각 행렬과 하부 삼각 행렬을 사용하여 역전파 과정을 단순화하고 Julia의 내장 함수를 활용하는 방법을 보여줍니다. 그는 선형 대수학을 사용하여 백슬래시가 하위 삼각 행렬을 풀 수 있는 방법을 시연하여 도함수 계산 작업을 훨씬 쉽게 만듭니다. Edelman은 선형 대수학이 많은 수학적 계산에 필수적이며 많은 복잡한 현상을 이해하는 비결이라고 강조합니다.
"1. 소개 및 행렬 곱셈"이라는 제목의 이 YouTube 동영상에서 강사는 성능 공학의 중요성과 시간이 지남에 따라 어떻게 발전해 왔는지에 대해 설명합니다. 연사는 매트릭스 곱셈의 예를 사용하여 코딩 기술과 기계 사양이 성능에 얼마나 큰 영향을 미칠 수 있는지 보여줍니다. 토론에서는 루프 순서, 캐시 사용 및 병렬 프로그래밍과 같은 주제를 다룹니다. 발표자는 또한 다양한 프로세서 및 산술 계산을 위해 코드를 최적화하는 방법을 탐색합니다. 전반적으로 비디오는 성능 공학의 세계와 최신 컴퓨팅 시스템에서의 실용적인 응용 프로그램에 대한 귀중한 통찰력을 제공합니다.
00:00:00 이 섹션에서 강사는 성능 공학의 중요성과 그것이 연구되는 이유에 대해 논의합니다. 소프트웨어 개발과 관련하여 성능이 항상 최우선 순위는 아닙니다. 그러나 그것은 컴퓨팅의 통화이며 프로그래밍의 용이성, 보안 및 정확성과 같은 원하는 다른 속성을 구매하는 데 사용됩니다. 성능 저하로 인해 소프트웨어를 사용할 수 없게 될 수 있으며 컴퓨팅 시스템에 대한 사람들의 주된 불만은 시스템이 너무 느리다는 것입니다. 따라서 성능은 본질적인 가치가 없을 수 있지만 개발자가 관심을 갖는 것에 기여합니다.
00:05:00 이 섹션에서 발표자는 컴퓨팅 성능 공학의 역사와 제한된 기계 자원으로 인한 초기의 집중적인 성능 공학에서 칩 밀도가 2년마다 두 배로 증가하고 대기하는 무어의 법칙 시대로의 전환에 대해 논의합니다. 하드웨어가 따라잡는 것이 소프트웨어를 최적화하는 것보다 더 유익했습니다. 그러나 발표자는 전력을 줄임으로써 클럭 속도를 더 높일 수 있는 Dennard 스케일링이 2004년에 끝났기 때문에 성능 엔지니어링의 필요성이 그 어느 때보다 중요하다고 지적합니다. 발표자는 컴퓨터 과학자인 Donald Knuth, Bill Wolfe 및 Michael Jackson의 인용문을 포함하여 읽기 쉬운 코드의 중요성과 조기 최적화에 대한 주의 사항에 대해 설명합니다.
00:10:00 이 섹션에서 발표자는 전력 밀도로 인해 2000년대 초에 도달한 클럭 속도의 한계에 대해 논의하여 성능 확장을 위한 멀티 코어 프로세서의 개발을 초래했습니다. 그러나 이것은 성능이 더 이상 무료가 아니며 병렬 프로그래밍이 필요하다는 것을 의미했으며, 이는 업계에서 이전에 수행하지 않았던 일입니다. 그 시점부터 소프트웨어는 새로운 하드웨어 구성에 적응해야 효과적이었고 그 결과 소프트웨어 개발 작업에서 성능에 대한 관심이 높아졌습니다.
00:15:00 이 섹션에서 연사는 최신 하드웨어를 효율적으로 사용하는 소프트웨어를 작성하는 방법을 배우는 것의 실용적이고 이론적인 중요성을 설명하는 것으로 시작합니다. 그런 다음 잘 연구된 행렬 곱셈 문제를 사용하여 성능 엔지니어링의 예를 제공하고 병렬 처리, 캐시 크기 및 메모리 용량과 같은 사양 및 기능을 포함하여 사용할 기계에 대해 논의하고 다음에 대한 설명으로 결론을 내립니다. 행렬 곱셈을 위한 파이썬의 기본 코드. 연사는 기계의 힘과 그 능력을 활용한 재미있는 프로젝트의 가능성을 강조합니다.
00:20:00 이 섹션에서 강사는 행렬 곱셈의 맥락에서 Python, Java 및 C++의 성능에 대해 논의합니다. 강의는 Python이 약 21,000초의 실행 시간으로 대규모 행렬 곱셈에 대해 너무 느리고, Java가 더 빠르고 Python보다 거의 9배 속도 향상을 제공하며, C++가 약 1,100초의 실행 시간으로 가장 빠르다는 것을 보여줍니다. , Java보다 2배 빠르고 Python보다 18배 빠릅니다.
00:25:00 이 섹션에서 화자는 Python과 같은 해석된 언어, C와 같은 컴파일된 언어, 바이트코드로 컴파일된 후 해석되는 Java와 같은 언어 간의 성능 차이에 대해 논의합니다. Python과 같은 인터프리터는 다재다능하지만 느리지만 C와 같은 컴파일러는 하드웨어 및 기계 명령어를 활용하여 성능을 최적화합니다. Java에서 사용되는 것과 같은 JIT 컴파일러는 가장 자주 실행되는 코드 조각만 컴파일하여 일부 성능을 복구합니다. 발표자는 Python의 성능 모델이 이해하기 어렵다고 지적합니다. 그래서 강의에서 성능 비교를 위해 C를 사용할 것입니다. 그러나 Python과 같은 관리 언어의 성능 엔지니어링에 대해 논의하는 게스트 강의가 있을 것입니다.
00:30:00 이 섹션에서는 행렬 곱셈에서 성능을 위한 루프 순서의 중요성에 대해 설명합니다. 루프의 순서는 실행 시간에 영향을 미치는 캐시 위치에 영향을 미칩니다. 행렬은 C에서는 행 우선 순서로, Fortran에서는 열 우선 순서로 메모리에 배치됩니다. 순서 ijk에 대한 액세스 패턴은 C에 대한 공간적 지역성이 우수하지만 B에 대한 공간적 지역성이 좋지 않습니다. "cachegrind" 도구는 코드의 미스율을 결정하는 데 유용하며 컴파일러 플래그 조정과 같은 간단한 변경으로 성능을 향상시킬 수도 있습니다.
00:35:00 이 섹션에서 발표자는 기계에서 더 나은 성능을 얻기 위해 코드를 최적화하는 방법에 대해 논의합니다. -O2 또는 -O3와 같은 좋은 최적화 플래그를 선택하는 것이 중요하지만 때때로 코드에 따라 더 낮은 최적화 플래그가 실제로 더 잘 최적화될 수 있습니다. 또한 실크 인프라를 사용하여 병렬 루프와 함께 멀티 코어 프로세서를 활용할 수 있으므로 18코어에서 거의 18배의 속도 향상이 가능합니다. 발표자는 내부 루프를 병렬화하는 것보다 외부 루프를 병렬화하는 것이 실제로 프로그램 속도를 저하시킬 수 있는 내부 루프를 병렬화하는 것보다 더 효과적이라고 강조합니다. 그러나 캐시 미스 및 벡터화된 명령을 효과적으로 사용하지 않는 것과 같은 최적화 기회의 원천이 여전히 있습니다.
00:40:00 이 섹션에서 발표자는 가능한 한 캐시의 데이터를 재사용하도록 계산을 재구성하여 캐시 미스를 더 잘 관리하는 방법에 대해 논의합니다. 타일링 방식을 사용하여 행렬을 더 작은 부분 행렬로 나누고 블록 단위로 곱하여 필요한 메모리 액세스 수를 줄입니다. 발표자는 부분 행렬의 크기를 결정하기 위해 튜닝 매개변수가 필요하다고 설명하고 최적의 값을 찾는 가장 좋은 방법은 실험이라고 제안합니다. 이 접근 방식을 통해 발표자는 동일한 크기의 공간을 계산하는 데 필요한 메모리 액세스 수를 크게 줄여 계산을 보다 효율적으로 만들 수 있음을 보여줍니다.
00:45:00 이 섹션에서는 발표자가 행렬 곱셈을 수행할 때 차단 또는 타일링을 사용하는 이점(예: 향상된 캐시 사용 및 더 빠른 실행 시간)에 대해 설명합니다. 그들은 칩이 가지고 있는 다양한 수준의 캐시와 프로그래머가 조정 매개변수를 사용하여 각 캐시 수준에 대한 코드를 최적화하는 방법을 설명합니다. 그러나 각 캐시 수준에 따라 조정 프로세스가 더 복잡해지고 코드를 읽고 이해하기 어려워질 수 있습니다. 발표자는 더 작은 하위 문제를 재귀적으로 해결하기 위해 병렬 프로그래밍을 사용하는 분할 및 정복 접근 방식을 제안합니다. 이 방법은 캐시 사용을 개선하지만 함수 호출의 오버헤드로 인해 계산 속도가 느려지므로 영리한 성능 엔지니어링의 필요성이 강조됩니다.
00:50:00 이 섹션에서 발표자는 분할 및 정복 기술을 사용하여 행렬 곱셈을 최적화하고 알고리즘을 사용하기 위한 임계값을 조정하는 방법에 대해 설명합니다. 임계값이 특정 숫자 미만인 경우 기본 사례가 설정되며 알고리즘은 일반 행렬 곱셈을 사용합니다. 기본 사례에 대한 최상의 값은 32로 확인되어 실행 시간이 1.3초이고 최고 성능의 12%가 되었습니다. 또한 연사는 단일 명령, 다중 데이터 형식으로 데이터를 처리하는 벡터 하드웨어를 사용하는 벡터화의 개념을 소개합니다. 발표자는 벡터화 보고서, 특정 아키텍처용 플래그, 컴파일러가 연결 순서를 재정렬할 수 있는 빠른 수학 플래그 사용을 포함하여 벡터화를 최적화하는 다양한 방법을 설명합니다. 아키텍처 고유의 빠른 수학을 사용하면 컴파일러 벡터화기를 사용할 때 성능이 두 배로 향상됩니다.
00:55:00 비디오의 이 섹션에서 발표자는 산술 계산에 사용되는 다양한 비트 크기에 대해 설명합니다. 64비트는 선형 대수 계산에 가장 일반적입니다. 그들은 또한 성능을 향상시키기 위해 AI 애플리케이션에 더 낮은 정밀도 산술을 사용할 수 있다고 언급합니다. 발표자는 최대 41%의 최고 성능과 약 50,000의 속도 향상을 제공하는 벡터 명령 및 AVX 내장 함수 사용에 대해 계속해서 이야기합니다. 그들은 행렬 곱셈에서 얻은 것과 유사한 성능 향상이 다른 영역에서는 볼 수 없을 수도 있지만 이 과정은 학생들에게 스스로 상당한 성능 향상을 달성하는 방법을 가르칠 것이라고 경고합니다. 또한 이 과정은 GPU 또는 기타 영역이 아닌 멀티 코어 컴퓨팅에 중점을 둡니다.
이 YouTube 비디오는 컴퓨터 프로그램을 위한 다양한 최적화 기술에 대해 설명합니다. 작업 최적화를 위한 Bentley 규칙이 도입되고 최적화가 데이터 구조, 루프, 논리 및 기능으로 그룹화됩니다. 값 인코딩, 데이터 구조 확장, 사전 계산, 캐싱 및 희소 행렬 활용과 같은 다양한 기술에 대해 설명합니다. 연사는 또한 그래픽 프로그램에서 그래프, 논리 최적화 및 충돌 감지 최적화를 위한 희소 행렬 표현 사용의 이점에 대해 설명합니다. 이러한 최적화 기술을 구현하면 프로그램의 실행 시간을 줄이고 효율성을 높일 수 있습니다.
비디오의 두 번째 부분에서는 루프 호이스팅, 루프에서 센티넬 사용, 루프 언롤링 및 퓨전, 함수 인라인을 비롯한 여러 범주의 최적화 기술을 다룹니다. 발표자는 조기 최적화에 대해 조언하고 정확성 유지 및 회귀 테스트 사용의 중요성을 강조합니다. 이 비디오는 또한 효율적인 방식으로 생산성을 높이고 목표를 달성하기 위한 6단계 가이드인 작업 최적화를 위한 Bentley 규칙을 간략하게 설명합니다. 이러한 규칙에는 명확한 목표 설정, 작업 세분화, 계획 및 구성, 작업 우선 순위 지정, 산만 최소화, 정기적인 접근 방식 검토 및 조정이 포함됩니다.
00:00:00 이 섹션에서 강사는 컴퓨터 프로그램 작업 최적화의 개념을 소개하고 프로그램 작업을 줄임으로써 성능을 향상시킬 수 있는 방법을 설명합니다. 그는 효율적인 프로그램 작성에 관한 책을 쓴 John Lewis Bentley의 이름을 딴 작업 최적화를 위한 Bentley 규칙에 대해서도 이야기합니다. 최적화는 데이터 구조, 루프, 논리 및 함수의 네 가지 범주로 그룹화되며 강사는 과정 전반에 걸쳐 일련의 미니 강의에서 22개의 규칙을 모두 다룰 계획입니다. 프로그램의 작업량을 줄이는 것은 실행 시간을 개선하기 위한 좋은 휴리스틱이지만 컴퓨터 하드웨어의 복잡한 특성은 이것이 항상 실행 시간의 감소로 해석되는 것은 아니라는 것을 의미하므로 강사는 나중에 아키텍처별 최적화도 다룰 것입니다. 강의.
00:05:00 비디오의 이 섹션에서 연사는 하나 이상의 데이터 값을 머신 워드에 저장하고 데이터 값을 더 적은 비트를 필요로 하는 표현으로 변환하기 위해 데이터 구조를 압축 및 인코딩하는 개념에 대해 설명합니다. 메모리에서 이동할 항목의 수를 줄임으로써 프로그램의 실행 시간을 줄이는 좋은 휴리스틱이 됩니다. 발표자는 특정 날짜의 월, 연도 또는 일을 쉽게 가져올 수 있도록 더 적은 비트를 사용하여 저장하는 인코딩 날짜의 예를 제공합니다. 연사는 C의 비트 필드 기능을 사용하여 구조화된 데이터를 저장하여 더 쉽게 액세스할 수 있도록 제안합니다. 이 표현에는 약간 더 많은 비트가 필요하지만 구조 내의 특정 데이터 값에 액세스하는 데 훨씬 더 효율적입니다.
00:10:00 이 섹션에서는 동영상에서 세 가지 최적화 기술에 대해 설명합니다. 첫 번째 기술은 값을 순차 정수로 인코딩할지 아니면 더 빠른 액세스를 위해 압축을 풀지 결정하는 것입니다. 두 번째 기술은 데이터 구조 확장으로, 데이터 구조에 정보를 추가하면 일반적인 작업을 최적화할 수 있습니다. 예를 들어 단일 연결 목록에 테일 포인터를 추가하여 두 개의 목록을 더 효율적으로 추가할 수 있습니다. 세 번째 기술은 사전 계산으로, 미션 크리티컬한 시간에 계산을 수행하지 않도록 미리 계산을 수행하는 것입니다. 예를 들어 파스칼의 삼각형을 사용하여 이항 계수를 사용하는 프로그램의 속도를 높이기 위해 이항 계수를 미리 계산합니다.
00:15:00 이 섹션에서 발표자는 재귀 공식과 C 코드를 사용하여 파스칼의 삼각형을 미리 계산하는 방법에 대해 설명합니다. 재귀 수식에는 선택 함수 호출과 루프를 사용하여 런타임 시 테이블을 미리 계산하는 방법이 포함된다고 설명합니다. 또한 소스 코드에 테이블 값을 입력하여 컴파일 시간에 테이블을 초기화하여 프로그램 실행 중에 시간을 절약하는 방법에 대해 설명합니다. 마지막으로 프로그램 실행 중에 액세스할 수 있는 최대 10개의 이항 계수의 예제 테이블을 제공합니다.
00:20:00 이 섹션에서 발표자는 큰 상수 값 테이블을 프로그램에 수동으로 입력하는 것을 방지하는 방법으로 메타 프로그래밍의 개념을 소개합니다. 필요한 코드를 생성하는 프로그램을 작성하면 지루한 작업을 자동으로 수행할 수 있습니다. 화자는 Python 코드 스니펫을 예로 제공합니다. 최근에 액세스한 결과를 캐시에 저장하여 비용이 많이 드는 계산을 반복하지 않도록 하는 기술로 캐싱 주제도 소개됩니다. 주어진 예는 제곱근 연산자를 사용하여 직각 삼각형의 빗변을 계산하는 것입니다. 여기서 캐시는 a 및 b 값과 함께 이전 빗변을 미리 저장합니다. 빗변 함수는 먼저 입력 값이 캐시의 값과 일치하는지 확인하고 일치하면 제곱근을 다시 계산할 필요 없이 캐시된 값을 반환합니다.
00:25:00 이 섹션에서 발표자는 프로그램에서 작업을 최적화하기 위한 캐싱의 개념에 대해 설명합니다. 일반적으로 계산된 값을 캐시에 저장함으로써 프로그램은 동일한 값을 반복적으로 계산하지 않아도 되므로 시간을 절약할 수 있습니다. 하드웨어도 캐싱을 수행하지만 소프트웨어도 캐싱을 수행할 수 있습니다. 예를 들어 가장 최근에 계산된 1,000개의 값을 저장하는 1,000 크기의 캐시가 있습니다. 동일한 값이 반복적으로 계산되면 최적화를 통해 프로그램 속도를 약 30% 높일 수 있습니다. 그런 다음 스피커는 입력의 희소성을 활용하여 해당 입력의 0 요소에 대한 컴퓨팅을 방지하여 계산 시간을 절약하는 아이디어를 소개합니다. 그들은 행렬 벡터 곱셈의 예를 통해 이를 시연하고 행렬 곱셈 속도를 높일 수 있는 압축된 희소 행(CSR) 데이터 구조를 소개합니다.
00:30:00 이 섹션에서 발표자는 CSR(Compressed Sparse Row) 형식을 사용하여 희소 행렬의 저장 및 계산 효율성을 최적화하는 방법에 대해 설명합니다. CSR 형식은 값 배열, 열 배열 및 행 배열의 세 가지 배열에 행렬의 0이 아닌 요소를 저장합니다. 연사는 행 길이를 계산하는 방법과 CSR 형식을 사용하여 행렬-벡터 곱셈을 수행하는 방법을 설명합니다. CSR 형식은 0이 아닌 요소의 수가 N^2보다 훨씬 적은 경우 조밀한 행렬 표현보다 공간 효율적일 수 있습니다. 그러나 상대적으로 조밀한 행렬의 경우 조밀한 행렬 표현이 더 적은 공간을 차지할 수 있습니다. 발표자는 CSR 형식을 사용하여 행렬-벡터 곱셈을 수행하기 위한 코드 예제를 제공합니다.
00:35:00 이 섹션에서 강사는 희소 행렬을 사용하여 그래프를 나타내는 이점과 너비 우선 검색 및 PageRank와 같은 고전적인 그래프 알고리즘을 보다 효율적으로 실행하는 데 활용할 수 있는 방법에 대해 설명합니다. 희소 그래프 표현은 오프셋과 가장자리의 두 가지 배열로 구성되며, 여기서 각 꼭지점의 각도는 연속 오프셋 간의 차이를 통해 얻을 수 있습니다. 에지의 가중치는 별도의 어레이에 저장하거나 캐시 집약성을 개선하기 위해 에지와 인터리브할 수도 있습니다. 이 섹션은 논리 최적화, 특히 실행 시간을 줄이기 위해 컴파일하는 동안 상수 식을 평가하는 상수 접기 및 전파에 대한 간략한 소개로 끝납니다.
00:40:00 비디오의 이 섹션에서 연사는 상수 접기 및 전파, 공통 하위 표현식 제거, 대수적 항등식 활용을 포함하여 코드에 대한 다양한 최적화 기술에 대해 논의합니다. 컴파일 타임에 상수를 정의함으로써 컴파일러는 상수를 평가하고 런타임 동안 시간을 절약할 수 있습니다. 공통 하위 표현식 제거를 사용하면 나중에 사용할 수 있도록 결과를 저장하여 동일한 표현식을 여러 번 계산하는 것을 피할 수 있습니다. 대수적 항등식을 이용하려면 더 비싼 표현을 더 저렴한 대안으로 대체해야 합니다. 연사는 컴파일러가 일반적으로 이러한 최적화를 구현하는 데 능숙하지만 컴파일러가 자동으로 수행하지 않는 상황에 대해 아는 것이 여전히 중요하다고 강조합니다.
00:45:00 비디오의 이 섹션에서 연사는 두 가지 최적화 기술에 대해 설명합니다. 첫 번째는 제곱근을 피하기 위해 대수적 항등식을 사용하여 계산 비용이 많이 드는 제곱근 연산자의 사용을 줄이는 것입니다. 두 번째 최적화 기술은 단락(Short-Circuiting)으로, 배열에 음수가 아닌 정수가 포함되어 있고 배열 값의 합계를 한계. 최적화는 배열의 모든 요소를 살펴볼 필요를 없애고 프로그램 실행 속도를 높일 수 있지만 테스트가 단락될 수 있는 빈도에 따라 신중하게 사용해야 합니다.
00:50:00 이 섹션에서는 논리 연산자 단락의 개념과 코드 최적화에 대한 유용성에 대해 설명합니다. 이중 앰퍼샌드 및 이중 세로 막대는 인수의 한쪽만 평가하여 시간과 리소스를 절약할 수 있는 단락 논리 연산자입니다. 또한 비디오는 성공 빈도와 실행 비용을 기준으로 테스트 주문을 제안합니다. 이 접근 방식은 비용이 덜 드는 테스트가 이미 실패한 경우 단락을 활용하여 비용이 많이 드는 테스트를 건너뛸 수 있습니다. 마지막으로 비디오는 결과가 이미 알려진 경우 검사를 사용하여 프로그램을 조기에 종료함으로써 빠른 경로를 생성하는 아이디어를 소개합니다. 이에 대한 예는 다른 충돌 조건을 확인하기 전에 두 공의 경계 상자가 교차하는지 확인하는 것입니다.
00:55:00 이 섹션에서 Bentley는 그래픽 프로그램에서 충돌 감지 테스트를 최적화하는 방법에 대해 설명합니다. 그는 더 비싼 충돌 테스트를 수행하기 전에 경계 상자가 교차하는지 확인하기 위해 빠른 경로 테스트를 제안합니다. 이 테스트에는 각 좌표의 차이의 절대값을 확인하고 두 반지름의 합보다 큰지 확인하는 작업이 포함됩니다. Bentley는 또한 단일 스위치 문 또는 심지어 테이블 조회를 통해 테스트를 결합하면 성능을 크게 향상시킬 수 있다고 지적합니다. 전반적으로 이러한 최적화는 많은 응용 프로그램 및 그래픽 프로그램에 도움이 될 수 있습니다.
01:00:00 이 섹션에서 비디오는 루프와 관련된 최적화의 세 번째 범주를 다룹니다. 논의된 첫 번째 루프 최적화는 루프 본문을 통해 매번 루프 불변 코드를 재계산하지 않도록 하는 호이스팅입니다. 식을 반복할 때마다 다시 계산하는 대신 한 번 계산하고 변수에 저장하면 실행 시간을 절약할 수 있습니다. 두 번째 루프 최적화는 경계 조건 처리를 단순화하고 루프 종료 테스트 처리 논리를 단순화하기 위해 데이터 구조에 배치된 특수 더미 값인 센티넬을 사용하는 것입니다. 배열에서 두 개의 추가 항목을 사용하도록 프로그램을 수정하면 센티널을 사용하여 루프가 반복될 때마다 한 번만 확인하면 됩니다.
01:05:00 이 섹션에서 발표자는 코드를 최적화하는 두 가지 기술인 경계 조건과 루프 풀기에 대해 설명합니다. 경계 조건에 대해 그는 입력 배열의 모든 요소가 0일 때 특수한 경우를 효율적으로 처리하기 위해 루프를 수정하는 방법을 보여줍니다. 배열 끝에 더미 요소를 추가하고 오버플로를 확인하면 코드에서 중지해야 하는 시점을 감지할 수 있습니다. 루프 언롤링의 경우 전체 및 부분의 두 가지 유형을 설명합니다. 더 큰 루프 크기로 인해 전체 루프 언롤링은 드물지만 부분 루프 언롤링은 여러 개를 하나로 결합하여 루프 반복 횟수를 줄여 실행되는 제어 흐름 명령의 수를 줄여 성능을 향상시킬 수 있습니다.
01:10:00 이 섹션에서 강사는 루프 언롤링 및 루프 융합 최적화에 대해 설명합니다. 루프 언롤링에는 루프의 여러 반복을 단일 반복으로 결합하여 루프 제어의 오버헤드를 줄이고 더 많은 컴파일러 최적화를 가능하게 합니다. 그러나 너무 많이 언롤링하면 명령 캐시를 오염시켜 성능에 부정적인 영향을 미칠 수 있습니다. 반면에 루프 융합은 동일한 인덱스 범위에 있는 여러 루프를 단일 루프로 결합하여 루프 제어 오버헤드를 줄이고 캐시 지역성을 향상시킵니다. 또한 강사는 빈 루프 본문에서 루프 반복 실행을 방지하기 위해 루프 범위를 수정하여 낭비되는 반복을 제거하는 방법에 대해 설명합니다.
01:15:00 이 섹션에서 Bentley는 함수 최적화, 특히 함수 호출의 오버헤드를 피하기 위한 인라인 개념에 대해 설명합니다. 함수를 정적 인라인으로 선언하면 컴파일러는 함수에 대한 호출을 함수 자체의 본문으로 대체하려고 시도하므로 별도의 함수 호출이 필요하지 않습니다. 매크로도 이 작업을 수행할 수 있지만 인라인 함수는 더 구조화되고 모든 인수를 평가하여 매크로가 비용이 많이 드는 식을 코드에 여러 번 붙여넣는 위험을 방지합니다. Bentley는 조기 최적화에 대해 조언하고 개발자에게 먼저 프로그램이 올바른지 확인하고 회귀 테스트를 사용하여 정확성을 유지하도록 권장합니다. 마지막으로 그는 많은 수준의 최적화가 컴파일러에 의해 자동화될 수 있으며 어셈블리 코드를 확인하면 그러한 최적화를 드러낼 수 있다고 지적합니다.
01:20:00 이 섹션에서는 작업 최적화를 위한 Bentley 규칙을 일련의 6단계로 설명합니다. 이러한 규칙은 명확한 목표 설정, 작업을 더 작은 부분으로 나누기, 계획 및 구성에 시간을 할애하기, 작업 우선 순위 지정, 산만함 최소화, 접근 방식을 정기적으로 검토 및 조정하는 것으로 구성됩니다. 이러한 지침을 따르면 보다 효율적인 방식으로 생산성을 높이고 목표를 달성할 수 있습니다. 또한 이러한 전략을 일상에 통합하면 강력한 직업 윤리를 유지하고 목표에 집중하는 데 도움이 될 수 있습니다.
이 YouTube 비디오는 이진 표현, 2의 보수, 비트 연산자, 임시 변수 없이 변수 교환, 코드 최적화를 비롯한 다양한 비트 조작 주제를 다룹니다. 이 비디오는 if-else 문을 사용하지 않고 최소 두 정수를 찾는 방법과 임시 변수를 사용하지 않고 두 정수를 바꾸는 방법과 같은 다양한 비트 트릭을 시연합니다. 발표자는 예측할 수 없는 분기에 대해 논의하고 예측 가능한 분기를 사용할 수 없는 경우를 위한 분기 없는 최소 비트 트릭을 소개하며 비트 해킹이 분할과 같은 비용이 많이 드는 작업을 단순한 비트 연산으로 대체하여 코드를 최적화할 수 있는 방법을 보여줍니다. 비디오는 또한 de Bruijn 시퀀스와 N Queens 문제와 같은 문제를 해결하는 데 적용하는 방법에 대해 설명합니다.
두 번째 부분에서는 비트 벡터를 사용하여 N Queens 문제를 해결하고 이진 단어에서 1비트의 수를 효율적으로 계산하는 방법에 대해 설명합니다. N Queens 문제를 구현하기 위해 역추적을 사용하고 보드를 효율적으로 표현하기 위해 비트 벡터를 사용합니다. N Queens 문제에서 여왕을 안전하게 배치하기 위한 세 가지 검사를 설명하고, 최하위 1비트를 재귀적으로 제거하여 단어의 1비트 수를 세는 방법을 제시합니다. 또한 테이블 조회 및 레지스터 조작을 사용하여 1비트 수를 계산하는 방법도 설명합니다. 비디오는 단어 길이의 로그 밑수 2에 비례하는 성능을 갖는 1비트를 계산하는 분할 정복 방식의 시연으로 끝납니다. 추가 학습을 위한 리소스도 제공됩니다.
00:00:00 이 섹션에서는 단어의 이진 표현과 단어에서 정수 값을 계산하는 방법에 대해 알아봅니다. 또한 부호 있는 정수에 대한 2의 보수 표현과 모두 0과 모두 1인 특수한 경우에 대해서도 배웁니다. 게다가, 우리는 X의 1의 보수에 대한 중요한 항등식과 2의 보수 표현에서 X의 음수와의 관계를 봅니다.
00:05:00 이 섹션에서 발표자는 1의 보수와 1의 보수에 1을 더하여 숫자의 음수를 얻는 방법을 설명합니다. 그는 또한 큰 이진 상수를 나타내는 데 16진수를 사용하는 방법을 살펴보고 16진수와 2진수 사이의 변환을 위한 표를 제공합니다. 그런 다음 비디오는 C++의 비트 연산자를 살펴보고 논리적 and, 논리적 or, 배타적 or, 왼쪽 및 오른쪽 시프트 연산에 사용하는 방법의 예를 보여줍니다.
00:10:00 이 섹션에서는 동영상에서 C의 비트 연산자를 사용하여 구현할 수 있는 다양한 일반 관용구에 대해 설명합니다. 한 가지 예는 시프트 다음에 OR 또는 NOT 및 그리고 각각. 또 다른 예는 원하는 비트의 위치에 1이 있고 다른 위치에 0이 있는 마스크를 생성한 다음 마스크를 X와 AND하고 추출된 비트를 오른쪽으로 이동하여 단어 X에서 비트 필드를 추출하는 것입니다. 비디오는 또한 이러한 트릭을 사용하는 것이 압축 또는 인코딩된 데이터로 작업할 때 특히 유용할 수 있다고 언급합니다.
00:15:00 이 섹션에서 비디오는 몇 가지 비트 트릭을 사용하여 임시 변수를 사용하지 않고 두 정수를 교환하는 방법에 대해 설명합니다. 이 코드는 X를 X XOR Y와 동일하게 설정한 다음 Y를 X XOR Y와 동일하게 설정하고 마지막으로 X를 X XOR Y와 동일하게 설정하는 작업을 포함합니다. 이것은 XOR 자체가 반전이고 첫 번째 줄은 X의 비트가 1인 마스크를 생성하기 때문에 작동합니다. 그리고 Y는 다릅니다. 그런 다음 X와 다른 Y의 비트를 뒤집는 데 사용됩니다. 이렇게 하면 임시 변수를 사용하지 않고 스왑이 가능합니다. 비디오는 또한 이러한 트릭으로 작업할 때 안전을 보장하기 위해 마스킹의 중요성을 강조합니다.
00:20:00 이 섹션에서 발표자는 두 가지 비트 핵에 대해 논의합니다. 첫 번째 해킹은 임시 변수를 사용하지 않고 두 개의 변수를 교환하는 방법입니다. 해킹에는 XOR과 마스크를 사용하여 두 변수 간에 다른 비트를 뒤집는 작업이 포함됩니다. 이 해킹은 멋지지만 명령 수준 병렬 처리가 좋지 않아 변수를 교환하는 가장 효율적인 방법은 아닙니다. 두 번째 해킹은 분기 예측 오류로 인해 성능 문제가 발생할 수 있는 if-else 문을 사용하지 않고 최소 두 개의 정수를 찾는 방법입니다. 대신 스피커는 비트 연산을 사용하여 정수를 비교하고 분기 없이 최소값을 계산하는 방법을 보여줍니다.
00:25:00 이 섹션에서 발표자는 두 개의 정렬된 배열을 병합하는 서브루틴에서 코드 최적화 및 "restrict" 키워드 사용에 대해 설명합니다. 이 프로세스는 두 개의 녹색 배열이 파란색 배열로 병합되는 예를 통해 설명됩니다. 코드의 각 분기의 예측 가능성에 대해서도 설명합니다. 첫 번째 분기는 예측 가능하고 두 번째 분기는 예측할 수 없습니다.
00:30:00 이 섹션에서는 비디오에서 프로그래밍의 예측 가능 및 예측 불가능한 분기에 대해 설명하고 예측 불가능한 분기 문제에 대한 솔루션으로 분기 없는 최소 비트 트릭을 소개합니다. 트릭은 "comp"라는 변수를 사용하여 a와 b의 첫 번째 요소 간의 비교 결과를 저장하고 비트 트릭을 사용하여 a와 b의 최소값을 얻는 것입니다. 그런 다음 C에 최소값을 배치하고 "comp" 값을 기준으로 A 또는 B의 값을 증가 또는 감소시킵니다. 이 비디오는 경우에 따라 트릭이 작동하지 않을 수 있지만 컴파일러가 수행하는 작업을 이해하는 데 도움이 되며 단어에 대한 많은 비트 해킹이 벡터에 대한 비트 및 워드 해킹으로 확장될 수 있으므로 이러한 트릭에 대해 아는 것이 유용하다고 설명합니다.
00:35:00 이 섹션에서는 비디오에서 비트 해킹과 프로그래밍에서의 유용성에 대해 설명합니다. 주어진 예제는 나눗셈을 사용하지 않고 더 빠른 작업을 허용하는 모듈식 추가를 위한 비트 트릭입니다. Z를 X와 Y의 합으로 설정한 다음 N보다 작거나 큰지 확인하면 프로그램은 범위 내에 있는 경우 Z를 반환하거나 Z 빼기 N의 결과를 반환하여 범위로 되돌릴 수 있습니다. 이 프로그램은 최소와 유사한 논리를 사용하며 분기 예측 오류를 초래할 수 있는 예측할 수 없는 분기가 있습니다. 주어진 또 다른 예는 N을 감소시키는 비트 조작을 사용하여 값을 가장 가까운 2의 거듭제곱으로 반올림하는 방법입니다. N을 다른 값으로 오른쪽으로 이동한 다음 비트 단위 또는 작업을 수행한 다음 끝에서 증가합니다.
00:40:00 비디오의 이 섹션에서 화자는 2비트 조작 문제에 대해 논의합니다. 첫 번째 문제는 주어진 값 n보다 큰 2의 최소 거듭제곱을 찾는 것입니다. 발표자는 비트 조작을 사용하고 n 빼기 1비트의 로그가 설정되도록 이미 2의 거듭제곱인 경우 n을 감소시켜 이를 달성하는 방법을 설명합니다. 두 번째 문제는 단어 X에서 가장 중요하지 않은 것의 마스크를 계산하는 것과 관련이 있으며 화자는 결과를 X로 설정하고 음의 X와 비트 및 연산을 사용하여 이를 달성하는 방법을 설명합니다. 화자는 인덱스를 찾는 코드도 제시합니다. X에 상수를 곱하고 테이블에서 결과를 찾아 비트를 계산합니다. 섹션은 스피커가 비트 조작과 관련된 수학 마술을 수행하는 것으로 끝납니다.
00:45:00 이 섹션에서 YouTube 동영상은 카드와 종으로 마술을 수행하는 그룹을 보여줍니다. 연기자는 청중의 마음을 읽었다고 주장하며 카드를 배포하기 전에 카드 덱을 자르라고 요청합니다. 퍼포머는 각 사람의 카드의 모양과 번호를 예측하고 겉보기에 성공한 것 같습니다. 그들은 "굉장한 onesie"와 마법 모자를 쓰고 종으로 공기를 맑게하는 능력을 자신의 능력으로 돌립니다.
00:50:00 이 섹션에서는 de Bruyne 시퀀스와 2의 거듭제곱의 로그 밑수 2 계산과의 상관 관계에 대해 알아봅니다. de Bruyne 시퀀스는 길이 K의 모든 가능한 비트 문자열이 정확히 발생하는 순환 비트 시퀀스입니다. 시퀀스의 하위 문자열로 한 번. 변환 테이블을 사용하여 de Bruyne 시퀀스 상수에 2의 거듭제곱을 곱하고 시퀀스의 시작 부분에 나타나는 하위 문자열을 추출하여 2의 거듭제곱의 로그 밑수 2를 계산할 수 있습니다. 시퀀스를 왼쪽으로 이동한 다음 찾아보면 변환 테이블에서 하위 문자열의 시작 위치 위로 올라가면 우리가 시작한 정수의 로그 밑수 2를 결정할 수 있으며, 이는 이전에 시연된 카드 트릭을 해결합니다.
00:55:00 이 섹션에서 발표자는 각 가능한 n비트 문자열을 정확히 한 번 포함하는 이진 알파벳의 순환 시퀀스인 de Bruijn 시퀀스에 대해 설명합니다. 시퀀스는 N Queens 문제와 같은 문제를 해결하는 데 사용할 수 있으며 마술을 사용하여 생성할 수 있습니다. 발표자는 또한 왼쪽 이동 후 de Bruijn 시퀀스의 하위 문자열 위치를 결정하기 위해 비트 트릭이 어떻게 작동하는지 설명합니다. 이 비트 트릭의 성능은 곱셈 및 테이블 조회 성능에 의해 제한되지만 이제는 이를 계산하는 하드웨어 명령이 있습니다.
01:00:00 이 섹션에서 발표자는 NxN 체스판에 N개의 체스 여왕을 배치하여 두 여왕이 서로를 위협하지 않도록 하는 N 여왕 문제에 대해 논의합니다. 문제는 종종 백트래킹을 사용하여 구현되는데, 여기서 퀸은 행별로 배치되고 프로그램은 유효한 위치를 찾을 수 없을 때 역추적합니다. 보드의 다른 표현도 논의되며 가장 컴팩트한 것은 3개의 비트 벡터 세트입니다. 아래쪽 벡터는 각 열의 여왕의 존재를 저장하고, 왼쪽 대각선 벡터는 각 왼쪽 대각선의 여왕의 존재를 저장하고, 오른쪽 대각선 벡터는 각 오른쪽 대각선의 여왕의 존재를 저장합니다. 비트 벡터를 사용하면 알고리즘을 보다 효율적으로 구현할 수 있습니다.
01:05:00 이 섹션에서는 비트 벡터를 사용하여 n-queens 문제에서 여왕을 배치하기에 안전한 위치인지 확인하는 과정을 설명합니다. 세 가지 확인에는 위치와 동일한 행, 동일한 열 및 동일한 대각선에 이미 여왕이 있는지 확인하는 것이 포함됩니다. 이 방법은 효율적이며 세 가지 검사를 모두 통과하면 여왕을 안전하게 배치할 수 있습니다. 논의된 또 다른 문제는 단어 X의 1비트 수를 세는 모집단 수입니다. 제시된 방법은 X의 최하위 1비트가 0이 될 때까지 반복적으로 제거하며 필요한 반복 횟수는 단어 X의 수에 비례합니다. X에서 1비트.
01:10:00 이 섹션에서 발표자는 테이블 조회를 사용하여 이진 단어의 1비트 수를 효율적으로 계산하는 방법에 대해 설명합니다. 테이블 조회 방법에는 각 8비트 단어에 1의 수를 저장하는 크기 256의 테이블을 만든 다음 이진 단어에서 각 8비트 하위 문자열에 대한 개수를 조회하는 작업이 포함됩니다. 발표자는 이 방법의 성능이 테이블에 액세스하는 데 필요한 메모리 작업으로 인해 병목 현상이 발생한다고 지적합니다. 연사는 계속해서 레지스터를 사용하여 1비트의 수를 세는 세 번째 방법을 제시합니다. 여기서 레지스터는 마스크를 만들고 메모리에 액세스하지 않고 이진 단어에서 1의 수를 세도록 하는 특정 명령을 실행합니다. 발표자는 예를 통해 이 방법이 어떻게 작동하는지 설명합니다.
01:15:00 이 섹션에서 화자는 병렬 분할 정복 방법을 사용하여 입력 단어에서 1의 수를 세는 방법을 시연합니다. 여기서 성능은 단어 길이 W의 로그 밑수 2에 비례합니다. 그것은 대부분의 최신 기계에는 컴파일러 내장을 통해 액세스할 수 있고 코딩할 수 있는 어떤 것보다 빠른 내장 팝 카운트 명령이 있다고 지적했습니다. 그러나 이렇게 하면 서로 다른 시스템 간에 코드 이식성이 떨어질 수 있습니다. 연사는 웹 사이트, 교과서, 체스 프로그래밍 웹 사이트 및 Hacker's Delight라는 책을 포함하여 비트 트릭에 대해 더 많이 배울 수 있는 몇 가지 리소스를 제공합니다.
이 비디오는 어셈블리 언어 및 컴퓨터 아키텍처에 대한 포괄적인 개요를 제공합니다. 어셈블리 언어는 코드 성능을 최적화하기 위한 중요한 인터페이스이며 컴퓨터 아키텍처를 이해하는 것은 어셈블리 언어를 마스터하는 데 필수적입니다. 연사는 x86 64 아키텍처의 역사와 개발, 키 레지스터, 데이터 유형, 메모리 주소 지정 모드, 명령어 세트 아키텍처(스택, 정수 및 이진 논리, 부울 논리 및 서브루틴 포함)에 대해 설명합니다. 또한 0 및 부호 확장과 같은 확장과 어셈블리 언어의 다양한 주소 지정 모드에 대해서도 설명합니다. 또한 비디오에서는 부동 소수점 유형, 벡터 및 벡터 단위, 기존 및 SSE 명령어, 수퍼스칼라 처리, 비순차 실행, 분기 예측과 같은 컴퓨터 아키텍처 설계 기능에 대해 설명합니다.
비디오는 또한 어셈블리 언어 및 컴퓨터 아키텍처와 관련된 여러 주제를 다룹니다. 중심 주제 중 하나는 데이터 종속성과 같은 위험으로 인해 발생하는 명령 수준 병렬 처리(ILP) 및 파이프라인 중단입니다. 발표자는 실제, 안티 및 출력 데이터 종속성과 수퍼 스칼라 프로세서가 하드웨어에서 더 많은 병렬성을 활용하여 한 번에 여러 명령을 실행할 수 있는 방법에 대해 논의합니다. 그러나 위험을 피하기 위해 아키텍트는 이름 변경 및 재정렬과 같은 전략과 브랜치의 결과를 추측하고 미리 실행하는 예측 실행을 구현했습니다. 연사는 청중이 소프트웨어 최적화를 더 잘 이해하기 위해 이러한 방법을 이해하도록 권장합니다.
00:00:00 이 섹션에서 강사는 현대 소프트웨어 과정에서 다루지 않는 어셈블리 언어 및 컴퓨터 아키텍처에 대해 이야기합니다. 이러한 개념을 이해하는 것은 코드 성능을 최적화하는 데 필요하며 어셈블리 언어는 이를 위한 최상의 인터페이스입니다. 코드를 컴파일하는 프로세스에는 전처리, 컴파일, 어셈블 및 링크를 포함한 여러 단계가 포함됩니다. 어셈블리 언어는 기계어 코드의 니모닉한 구조로 사람이 가독성을 높인 형태로 LD 명령어를 이용한 연결 단계를 거쳐 최종 실행 파일이 생성된다.
00:05:00 이 섹션에서 발표자는 어셈블리와 기계 코드가 기계 코드의 특정 비트 패턴에 해당하는 어셈블리의 OP 코드와 함께 구조가 매우 유사하다고 설명합니다. 연사는 기계 코드의 분해를 생성할 수 있는 프로그램 ABS를 소개하여 니모닉하고 사람이 읽을 수 있는 조립 코드를 공개합니다. 그런 다음 연사는 컴파일러가 수행한 작업과 수행하지 않은 작업 공개, 컴파일러 오류 디버깅, 소스에 액세스하지 않고 프로그램을 리버스 엔지니어링하는 등 어셈블리 코드를 보고자 하는 몇 가지 이유에 대해 논의합니다.
00:10:00 이 섹션에서 발표자는 클래스에 대한 기대치를 설명합니다. 여기에는 컴파일러가 x86 명령어로 언어 구조를 구현하는 방법 이해, x86 어셈블리 언어 읽기 가능, 일반적인 어셈블리 패턴의 성능 영향 이해가 포함됩니다. 학생들은 필요한 경우 처음부터 코드를 작성할 수 있어야 하며 이것이 가능한 수준까지 마스터할 수 있어야 합니다. 그런 다음 스피커는 레지스터, 명령어, 데이터 유형 및 메모리 주소 지정 모드를 포함하는 x86 64 명령어 세트 아키텍처에 대해 설명합니다. 키 레지스터에는 범용 레지스터와 산술 연산을 추적하고 운반하는 플래그 레지스터가 포함됩니다. 명령어 포인터는 어셈블리 언어 프로그램의 명령어 시퀀스를 통해 하드웨어를 안내합니다.
00:15:00 이 섹션에서 발표자는 x86 64 아키텍처의 역사와 메모리가 제한된 16비트 워드 머신에서 더 많은 메모리를 사용할 수 있게 됨에 따라 인덱싱을 위한 더 넓은 단어로의 개발에 대해 논의합니다. 연사는 또한 벡터화를 위한 xmm 및 AVX 레지스터와 같은 벡터 레지스터의 추가와 사용 방법에 대해 설명합니다. 또한 범용 레지스터의 주제와 기능적 목적이 시간이 지남에 따라 크게 변경되었지만 역사적 이유로 인해 이름이 그대로 유지되는 방법에 대해서도 다룹니다. 또한 발표자는 짧은 단어, 32비트 또는 64비트 단어의 하위 및 상위 절반에 대해 특정 레지스터가 동일한 것으로 어떻게 앨리어싱되는지 설명합니다.
00:20:00 이 섹션에서 발표자는 x86 64 어셈블리 언어의 기본 사항과 작동 방식을 설명합니다. 레지스터는 레지스터의 어느 부분이 액세스되고 있는지에 따라 다른 이름을 가지며 일부는 스택 포인터로 사용되는 RSP와 같은 특정 목적을 가지고 있습니다. x86 64 명령 코드의 형식은 일반적으로 소스 또는 대상이 될 수 있는 0-3 피연산자와 함께 opcode 및 피연산자 목록을 갖는 것입니다. 연사는 작업을 참조하기 위한 AT&T 구문과 Intel 구문의 차이점을 설명하고 "이동" 및 "조건부 이동"과 같은 일반적인 op 코드 목록을 제공합니다. 또한 발표자는 32비트 값 레지스터에서 64비트 레지스터로 이동할 때 부호 확장의 중요성을 설명합니다.
00:25:00 이 섹션에서 발표자는 스택, 정수 산술, 이진 논리, 부울 논리, 점프 및 서브루틴에 대한 명령을 포함하여 어셈블리 언어의 다양한 유형의 명령에 대해 설명합니다. opcode는 연산 또는 조건 코드의 데이터 유형을 설명하는 접미사로 보강될 수 있습니다. 예를 들어 "큐"가 있는 이동은 이동 중인 데이터가 8바이트 또는 64비트로 구성된 쿼드 워드임을 나타냅니다. x86 64 데이터 유형과 해당 어셈블리 접미사에 대해서도 설명하고 기호 확장이 작동하는 방식을 설명하기 위한 예제가 제공됩니다. 어셈블리 언어에서 특정 opcode 및 니모닉의 존재 여부는 혼란스러울 수 있지만 컴파일러는 프로그램을 올바르게 실행하기 위해 이러한 명령을 이해해야 합니다.
00:30:00 이 섹션에서 발표자는 32비트 작업을 64비트 작업으로 이동할 때 발생하는 제로 확장 및 부호 확장과 같은 확장에 대해 설명합니다. 또한 새로운 명령어를 추가하면 Intel 명령어 세트가 어떻게 더 복잡해질 수 있는지 언급합니다. 연사는 계속해서 조건부 점프 및 조건부 이동에 사용되는 다양한 조건 코드와 함께 사용되는 플래그(예: 제로 플래그 및 오버플로 플래그)를 설명합니다. 제로 플래그를 확인하는 특정 조건 코드에 대한 이유도 설명합니다.
00:35:00 이 섹션에서 발표자는 어셈블리 언어의 다양한 직접 및 간접 주소 지정 모드에 대해 설명합니다. 직접 주소 지정 모드에는 즉시, 직접 메모리 및 레지스터 사용이 포함됩니다. 레지스터 간접 및 레지스터 인덱싱 주소 지정 모드를 사용하면 레지스터에 주소를 제공하거나 주소를 오프셋하여 메모리에 액세스할 수 있습니다. 발표자는 메모리 액세스가 느리고 비용이 많이 들 수 있으므로 프로세스 속도를 높이려면 가능할 때마다 레지스터에 값을 저장하는 것이 중요하다고 말합니다. 또한 메모리 액세스를 최적화할 때 캐싱의 중요성에 대해서도 언급합니다.
00:40:00 이 섹션에서는 지침 포인터가 범용 레지스터가 아닌 데이터를 인덱싱하는 데 사용되는 포인터 관련 인덱싱의 사용에 대해 비디오에서 설명합니다. 기본 포인터에서 부드러운 인덱싱을 지원하는 복잡한 명령인 기본 인덱스 스케일 변위 주소 지정 방법도 도입되었습니다. 비디오는 레지스터를 제로화하는 데 사용되는 XOR opcode와 비트 및 두 값을 계산하고 레지스터 플래그를 보존하는 테스트 opcode를 포함하여 일부 어셈블리 언어 관용구에 대한 개요를 제공합니다. 마지막으로 비디오는 코드에서 제어 흐름을 허용하는 점프 지침 및 레이블을 다룹니다.
00:45:00 이 섹션에서는 비디오에서 다양한 명령 집합과 부동 소수점의 역사를 포함하여 어셈블리 언어와 컴퓨터 아키텍처에 대해 설명합니다. x87 및 SSE를 포함한 x86 명령어 세트는 단일 및 이중 정밀도 스칼라 부동 소수점 산술 및 벡터 명령어를 지원합니다. SSE 명령어는 컴파일 및 최적화의 단순성으로 인해 일반적으로 x87보다 컴파일러에서 선호됩니다. 정렬 최적화와 같이 어셈블리에서 작업(nop) 명령을 사용하지 않는 목적도 설명합니다.
00:50:00 이 섹션에서 발표자는 컴퓨터 아키텍처에서 사용되는 부동 소수점 유형, 벡터 및 벡터 단위에 대해 설명합니다. 발표자는 벡터 장치가 작동하는 방식은 프로세서가 각각 레인이라고 하는 모든 벡터 장치에 명령을 내리는 것이라고 설명합니다. 레인에는 정수 또는 부동 소수점 산술이 포함되어 있으며 모두 동일한 작업을 수행한다는 의미인 록스텝으로 작동합니다. 한 번에 여러 작업을 수행할 수 있으며 이 모든 작업을 단일 명령으로 수행할 수 있습니다. 발표자는 일부 아키텍처에서는 벡터 피연산자를 정렬해야 하는 반면 다른 아키텍처에서는 메모리의 벡터를 이동할 수 있어 둘 사이의 성능 차이가 발생한다고 설명합니다. 또한 순열, 섞기 및 분산 수집과 같은 교차 레인 작업을 지원하는 아키텍처가 있습니다.
00:55:00 이 섹션에서 발표자는 기존 명령어와 SSE 명령어의 차이점과 사용 방법에 대해 설명합니다. 그들은 또한 ymm이 별칭 xmm 레지스터를 등록하고 avx-512를 사용하여 512비트로 확장하는 앨리어싱 트릭을 언급합니다. 그런 다음 컴퓨터 아키텍처, 특히 5단계 파이프라인과 14~19개의 파이프라인 단계를 특징으로 하는 최신 프로세서 간의 차이점에 대한 토론으로 이동합니다. 그들이 논의하는 설계 기능에는 벡터 또는 하드웨어 I, 수퍼스칼라 처리, 비순차 실행 및 분기 예측이 포함되지만 시간 제약으로 인해 비순차 실행에 대해 깊이 파고들지는 않을 것이라고 언급합니다.
01:00:00 비디오의 이 섹션에서 강사는 명령 수준 병렬 처리(ILP) 및 파이프라인 중단에 대해 설명합니다. ILP에는 처리량을 향상시키기 위해 여러 명령을 동시에 실행할 기회를 찾는 것이 포함됩니다. 그러나 파이프라인 지연은 구조적 위험, 데이터 위험 또는 제어 위험과 같은 위험으로 인해 명령을 실행할 수 없을 때 발생할 수 있으며 데이터 위험이 가장 일반적입니다. 명령이 쓰기 종속 이후에 읽을 때 진정한 종속이 발생하는 반면, 반의존은 명령이 위치에 쓰기를 원하지만 이전 명령이 값을 읽을 때까지 기다려야 할 때 발생합니다. 컴파일러는 위험을 피하기 위해 코드를 최적화하여 파이프라인 중단을 줄이려고 시도합니다.
01:05:00 이 섹션에서는 어셈블리 언어의 데이터 종속성 개념에 대해 설명합니다. 세 가지 유형의 데이터 종속성이 있습니다: true, anti 및 output. 산술 연산, 특히 부동 소수점 산술과 같은 복잡한 연산은 대기 시간이 더 길고 프로세서에 별도의 기능 장치가 필요하며 때로는 별도의 레지스터가 필요합니다. 명령 수준 병렬성을 높이기 위해 설계자는 사이클당 여러 명령을 발행하여 하드웨어에서 더 많은 병렬성을 활용하는 것과 같은 기술을 구현했습니다.
01:10:00 이 섹션에서 비디오는 Haswell이 명령어를 마이크로 연산이라는 더 간단한 작업으로 나누고 주기당 최대 4개의 마이크로 연산을 방출하는 예를 사용하여 수퍼 스칼라 프로세서가 한 번에 여러 명령어를 실행할 수 있는 방법을 설명합니다. 그런 다음 비디오는 프로세서가 명령을 순서대로 실행하지 못하도록 하는 전략을 자세히 설명합니다. 바이패싱 및 레지스터 이름 변경을 포함하여 종속되지 않은 명령을 순서대로 실행하여 처리 시간을 단축할 수 있습니다. 이러한 전략에는 종속성을 추적하고 데이터 종속성과 같은 위험을 피하는 방식으로 코드를 실행해야 합니다.
01:15:00 이 섹션에서 연사는 데이터 위험을 방지하기 위해 최신 프로세서에서 사용되는 두 가지 중요한 방법인 이름 바꾸기 및 재정렬에 대해 설명합니다. 발표자는 분기 예측에 사용되어 지연을 방지하기 위해 분기의 결과를 추측하고 미리 실행하는 예측 실행에 대해서도 이야기합니다. 그러나 추측이 틀리면 계산을 취소하는 데 약 15~20사이클의 비용이 소요됩니다. 연사는 분기 예측기가 작동하는 방식을 간략하게 언급하지만 복잡하고 추가 연구가 필요함을 지적합니다. 급하게 끝났음에도 불구하고 연사는 청중이 다양한 방법을 이해하도록 격려하며 이는 특정 소프트웨어 최적화가 작동하고 작동하지 않는 이유를 이해하는 데 도움이 될 것입니다.
비디오의 이 부분에서는 컴파일러를 사용하여 어셈블리 언어에서 C 코드를 구현하는 방법과 함께 어셈블리 언어에 대한 C 이해의 중요성에 대해 설명합니다. 초점은 특히 Linux x86 64 호출 규칙에서 LLVM IR이 어셈블리로 변환되는 방식에 있습니다. 발표자는 LLVM IR의 기본 구성 요소와 C 프로그래밍 언어의 구문이 LLVM IR로 변환되는 방법을 설명합니다. 비디오는 또한 가상 메모리의 레이아웃, 여러 함수 간의 함수 호출 조정 문제, Linux x86 64 호출 규칙의 두 포인터(BP 및 SP)를 사용하여 모든 스택 프레임을 관리하는 방법을 다룹니다.
이 비디오는 또한 레지스터를 호출자 저장 또는 수신자 저장으로 저장하는 것과 같이 C에서 어셈블리 프로그래밍으로 레지스터 상태를 유지하기 위한 전략과 x86 호출 규칙이 작업 낭비를 방지하는 방법을 설명합니다. C 및 어셈블리에서 함수 호출이 작동하는 방식을 다루고 인수 및 로컬 변수를 스택에 저장하는 프로세스와 기본 포인터 대신 스택 포인터를 사용하는 일반적인 최적화에 대해 설명합니다. 비디오는 또한 제어 흐름 그래프를 사용하여 LV miR을 어셈블리 코드로 컴파일하고 함수 프롤로그에 대해 논의하고 레지스터를 저장하고 조건을 처리하고 C 코드를 어셈블리 코드로 변환하는 과정을 보여줍니다. 마지막으로 결과를 반환하기 전에 레지스터를 복원하는 데 사용되는 함수 에필로그에 대해 설명합니다.
00:00:00 비디오의 이 섹션에서 TB Shuttle은 어셈블리 언어에 대한 C 이해의 중요성에 대해 설명합니다. 그는 어셈블리 언어가 C 코드보다 더 정밀하며 C 코드에서 명확하지 않은 프로그램에 대한 세부 정보를 밝힐 수 있다고 지적합니다. 어셈블리를 살펴보면 개발자가 프로그램을 최적화할 때 컴파일러가 수행한 작업과 수행하지 않은 작업을 결정할 수도 있습니다. 또한 특정 수준에서 코드를 최적화할 때만 예기치 않은 동작을 생성하는 버그가 발생할 수 있으므로 이러한 버그를 발견하기 어렵습니다. 마지막으로 어셈블리를 이해하면 개발자가 어셈블리 코드를 직접 수정하거나 코드를 리버스 엔지니어링할 수 있습니다.
00:05:00 이 섹션에서는 사용할 어셈블리 명령, C 조건 및 루프 구현 방법, 함수 호출을 조정합니다. 번역 프로세스를 이해하기 위해 비디오에서는 컴파일러가 프로그램에 대해 추론하는 데 사용하는 단순화된 어셈블리인 LVM IR을 소개합니다. 그런 다음 비디오는 함수, 조건 및 루프와 같은 C 프로그래밍 언어의 구문이 LVM IR로 변환되는 방법을 설명합니다. 이 섹션은 LVM IR 속성에 대한 간략한 언급으로 끝납니다.
00:10:00 이 섹션에서는 특히 Linux x86 64 호출 규칙에서 LLVM ir가 어셈블리로 변환되는 프로세스에 중점을 둡니다. 발표자는 LLVM ir에 대한 간략한 입문서를 제공하여 간단한 어셈블리 버전과 유사한 함수, 명령 및 레지스터의 기본 구성 요소를 설명합니다. LLVM ir 레지스터는 c 변수와 유사하며 이름으로 구별되며 각 함수에는 자체 로컬 레지스터 이름이 있습니다. 발표자는 예제 코드 스니펫에서 레지스터를 강조 표시하고 LLVM의 다른 기본 블록을 참조할 때 레지스터 구문이 하이재킹된다는 점에 주목합니다. 강연은 피보나치 수를 계산하는 간단한 코드에서 이 프로세스가 어떻게 작동하는지에 대한 사례 연구로 끝납니다.
00:15:00 이 섹션에서 발표자는 레지스터 이름, 등호, opcode 및 피연산자 목록을 포함하는 LV Mir 명령어의 구문을 설명합니다. 일부 명령어는 로컬 레지스터에 저장되는 값을 반환하지만 다른 명령어는 그렇지 않습니다. LV Mir 명령어 세트는 데이터 이동, 산술 및 논리 연산, 제어 흐름에 대한 몇 가지 명령어만 포함하기 때문에 x86보다 작습니다. LV Mir에서는 모든 것이 정수(정의된 비트 수 포함), 부동 소수점 유형, 포인터 유형, 벡터 유형 및 기본 블록의 레이블 유형을 포함하는 유형으로 노출됩니다. 발표자는 또한 LV Mir 벡터 연산이 SSE나 AVX처럼 보이지 않고 오히려 벡터 유형에서 작동하는 일반적인 연산처럼 보인다고 언급합니다.
00:20:00 이 섹션에서는 비디오에서 C 코드의 작업 시퀀스가 LLVM IR로 변환되는 방법과 IR에서 코드를 해석하기 위한 경험 법칙에 대해 설명합니다. 또한 발췌문에서는 LLVM IR이 배열 및 구조체와 같은 기본 및 집계 유형을 처리하는 방법을 설명하고 배열의 요소에 액세스하는 데 메모리의 주소 계산이 어떻게 관련되는지에 대한 예를 보여줍니다. 또한 비디오는 C 함수가 LLVM IR로 변환되는 방법과 두 언어의 해당 반환 문을 설명합니다.
00:25:00 이 섹션에서 비디오는 C의 기능과 매개변수가 LV Mir로 변환되는 방법을 설명합니다. LV Mir의 기능은 C의 기능과 유사하지만 C 매개변수는 LV Mir의 매개변수 목록이 됩니다. 그러나 레지스터의 이름이 잘 지정되지 않아 해독하기 어렵기 때문에 LV Mir를 읽는 것이 어려울 수 있습니다. 이 비디오는 제어 흐름 지침에 따라 분할된 코드 청크인 LV Mir의 기본 블록에 대해서도 설명합니다. 기본 블록 간의 연결은 분기 명령에 의해 유도된 에지를 기반으로 합니다. 마지막으로 비디오는 LV Mir의 조건문을 다룹니다. 여기서 if-then-else 문은 기본 블록 및 제어 흐름 에지를 유도하는 조건부 분기 명령이 됩니다.
00:30:00 이 섹션에서 동영상은 LLVM IR에서 조건부 연산 및 분기가 작동하는 방식을 설명합니다. 이 프로세스는 리터럴 값과 레지스터에 저장된 값을 비교하여 시작하여 1비트 정수 또는 부울 결과를 생성합니다. 그런 다음 이 결과는 술어가 참인지 거짓인지를 나타내는 기본 블록의 두 레이블과 함께 조건부 분기 작업에 전달됩니다. 피연산자가 하나인 무조건 분기가 있는 경우 결과는 특정 기본 블록으로 직접 점프합니다. 영상은 또한 조건문이 있을 때마다 제어 흐름 그래프에서 다이아몬드 모양을 만드는 방법을 보여주고 C 코드로 작성된 루프의 예를 제공합니다.
00:35:00 이 섹션에서는 비디오에서 루프 본문과 루프 컨트롤을 포함하는 C 루프의 구성 요소에 대해 설명합니다. 루프 본문은 각 반복에서 실행되는 반면 루프 제어는 루프의 모든 반복을 관리합니다. AC 루프는 제어 흐름 그래프에서 루프 패턴을 생성하며, 이는 다시 LLVM ir에서 루프 구조를 생성합니다. 그런 다음 비디오는 루프 제어를 위한 LLVM ir 코드를 분석합니다. 여기서 루프를 처리할 때 일반적으로 발생하는 이상한 명령이 있습니다. fie 명령은 코드의 LLVM 표현 문제를 해결하려고 시도합니다. 여기서 I는 여러 레지스터로 표시되어 실제로 어디로 갔는지 명확하지 않습니다.
00:40:00 이 섹션에서 동영상은 루프의 유도 변수를 LLVM의 다양한 위치에 매핑하는 방법을 설명합니다. 이는 루프 반복에서 변수의 값이 변경되기 때문입니다. 이로 인해 각 명령이 레지스터 값을 한 번만 정의하는 LLVM의 "정적 단일 할당" 불변이 발생하여 유도 변수에 문제가 발생합니다. "phi" 명령은 제어 흐름이 루프의 진입점에서 병합되는 방식에 따라 레지스터 값을 정의하여 이 문제를 해결합니다. 비디오는 또한 LLVM의 속성과 "추가" 명령어에 연결된 NSW 속성과 같은 LLVM 구성에 대한 추가 정보를 제공하는 방법에 대해 설명합니다.
00:45:00 비디오의 이 섹션에서는 어셈블리와 유사하지만 모든 계산된 값이 일반 C 변수와 같은 레지스터에 저장되기 때문에 여러 면에서 더 간단한 LLVM IR에 중점을 둡니다. LLVM IR은 각 변수가 최대 하나의 명령으로 작성되는 정적 단일 할당 패러다임을 사용합니다. 이 비디오는 C 코드를 LLVM IR로 변환한 다음 어셈블리로 변환하는 방법을 설명하며 프로세스에 약간의 복잡성이 추가됩니다. 컴파일러는 LLVM IR 작업에 필요한 실제 어셈블리 명령을 선택하고, 사용할 범용 레지스터를 결정하고, 서로 다른 소스 파일과 이진 라이브러리 간의 함수 호출을 조정합니다. 그런 다음 토론은 Linux x86 64 호출 규칙으로 바뀝니다.
00:50:00 이 섹션에서는 프로그램의 가상 메모리 레이아웃에 대해 설명합니다. 가상 메모리는 어셈블리 코드에서 어셈블러 지시문을 사용하여 구성되는 스택 및 힙 세그먼트와 같은 세그먼트로 나뉩니다. 또한 메모리를 할당하고 값을 저장하는 공간 지시문 및 긴 세그먼트와 같은 다양한 유형의 저장 지시문에 대해 설명합니다. 그런 다음 로컬 변수, 함수 인수, 반환 주소 및 가능한 중간 결과 저장을 포함하는 함수 호출 및 반환을 관리하기 위해 데이터가 저장되는 스택 세그먼트에 주의를 기울입니다.
00:55:00 비디오의 이 섹션에서 발표자는 여러 함수에서 함수 호출을 조정하는 문제에 대해 논의합니다. 이 중 일부는 다른 파일이나 라이브러리에서 발생할 수 있습니다. 모든 함수가 잘 작동하도록 하기 위해 모든 함수가 준수해야 하는 호출 규칙이 설정되었습니다. Linux x86 64 호출 규칙은 두 개의 포인터(BP 및 SP)를 사용하여 각 함수 인스턴스화에 대한 모든 스택 프레임을 관리합니다. 호출 명령이 실행되면 IP의 현재 값이 반환 주소로 스택에 푸시되고 호출 명령은 프로그램 메모리의 일부 함수 주소로 점프합니다. 반환 명령은 호출 명령의 작업을 실행 취소하고 스택에서 반환 주소를 팝하여 호출자의 실행으로 돌아갑니다. 동일한 기능을 사용하려는 여러 기능의 문제를 처리하려면 레지스터, 호출 규칙은 각 함수가 사용할 수 있는 레지스터에 대한 규칙과 함수 호출을 통해 해당 레지스터를 보존하는 방법을 자세히 설명합니다.
01:00:00 이 섹션에서 비디오는 C에서 어셈블리 프로그래밍에 이르기까지 다양한 기능으로 작동할 때 레지스터 상태를 유지하기 위한 전략에 대해 설명합니다. 사용할 수 있는 두 가지 방법, 즉 호출자가 호출을 호출하기 전에 등록 상태를 저장하는 방법과 호출 수신자가 모든 등록 상태를 저장하는 방법에 대해 언급합니다. x86 호출 규칙에는 작업 낭비를 피하기 위해 일부 레지스터를 호출 수신자 저장으로 지정하고 다른 레지스터를 호출자 저장으로 지정하는 두 가지가 모두 포함됩니다. 비디오는 또한 스택 메모리가 구성되는 방식과 스택이 커지는 방식을 살펴봅니다. 마지막으로 함수가 스택 메모리의 겹치는 부분을 사용하는 방법을 조정하는 방법에 대해 설명합니다.
01:05:00 이 섹션에서 동영상은 C 및 어셈블리에서 함수 호출이 작동하는 방식에 대해 설명합니다. 함수 C를 호출하기 전에 함수 B는 로컬 변수 아래 자체 스택 메모리의 예약된 연결 블록에 함수 C에 대한 비등록 인수를 배치합니다. 음수 오프셋으로 해당 인수에 액세스합니다. 함수 C가 시작되면 B의 스택 프레임에 대한 기본 포인터를 저장하고 새 프레임에 들어가므로 BP를 SP와 동일하게 설정하는 함수 프롤로그를 실행합니다. 그런 다음 자체 로컬 변수를 위한 스택 공간과 B가 호출자 또는 호출 대상을 위해 만드는 연결 블록에 사용할 공간을 할당합니다. 비디오는 또한 컴파일러가 BP를 제거하고 하나 이상의 범용 레지스터를 얻기 위해 스택 포인터 RSP를 기반으로 모든 인덱싱을 수행할 수 있는 일반적인 최적화를 언급합니다.
01:10:00 이 섹션에서 강사는 LV miR을 어셈블리 코드로 컴파일하는 과정을 통해 청중을 안내합니다. 첫 번째 단계는 전역 fib 지시문 및 정렬과 같은 일부 어셈블러 지시문을 사용하여 'fib' 함수를 전역적으로 액세스 가능한 함수로 정의하는 것입니다. 그런 다음 함수 프롤로그는 var BP의 푸시 큐와 RSP rbp의 mob 큐와 함께 저장됩니다. 어셈블리 코드는 인수를 RTI 함수로 이동하기 전에 Kali-save 레지스터인 스택에 두 개의 레지스터를 푸시하고 RBX 레지스터로 squirrels합니다. 마지막으로 N의 값이 2보다 작은지 비교 명령어를 평가하여 2보다 작은 경우 입력값을 반환한다. 그렇지 않으면 직선 코드를 통해 n 빼기 1의 fib와 n 빼기 2의 fib를 계산하고 함께 더한 다음 그 결과를 반환합니다.
01:15:00 이 섹션에서 비디오는 조건부 점프와 비교 결과에 따라 코드에서 다음에 발생하는 다양한 동작에 대해 설명합니다. JGE 명령은 n이 2보다 크거나 같을 때 LLVM 분기 연산의 거짓 측에 대한 레이블로 점프하는 반면, 연산은 n이 2보다 작을 때 연산의 참 측에 해당합니다. LEA 명령은 다음에 사용됩니다. 주소 계산, 이동 작업은 함수 호출 결과를 R14에 저장합니다. 다음 명령어 세트는 n-2의 값을 계산하고 RDI에 보관한 다음 n-2에서 fib를 호출하여 결과를 AX로 반환합니다. 마지막으로 작업은 R14를 AX에 추가합니다.
01:20:00 이 섹션에서 비디오는 C 코드에서 어셈블리 코드로의 변환에 대해 설명합니다. 발표자는 프로세스가 제어 흐름 에지로 연결된 기본 블록으로 구성된 제어 흐름 그래프를 사용하여 코드를 표현한다고 설명합니다. 또한 어셈블리 코드에서 호출 규칙을 처리하는 복잡성에 대해서도 언급합니다. 함수 에필로그는 결과를 반환하기 전에 스택 프레임의 어떤 것보다 먼저 레지스터를 복원하는 데 사용됩니다. 비디오는 섹션 전체에서 다루는 주요 주제를 요약하여 마무리합니다.
이 동영상 강의에서는 멀티코어 프로그래밍과 무어의 법칙으로 인한 멀티코어 프로세서의 등장과 클록 주파수 스케일링의 종말에 대해 설명합니다. 발표자는 프로세서가 직면한 전력 밀도 문제와 무어의 법칙을 따라가기 위해 칩에 다중 코어를 추가하게 된 방법을 설명합니다. 강의는 또한 병렬 프로그래밍을 위한 추상화를 제공하는 Pthreads, TBB, OpenMP 및 Silk와 같은 공유 메모리 하드웨어 및 동시성 플랫폼의 캐시 일관성 프로토콜의 기본 사항을 다룹니다. 피보나치 프로그램을 구현하는 예를 통해 각 플랫폼의 장단점을 논의하고 시연합니다. 이 비디오는 멀티 코어 프로그래밍에 대한 포괄적인 개요와 프로그래머가 직면한 문제 및 솔루션을 제공합니다.
비디오는 또한 병렬 처리를 처리하기 위한 추상화 도구인 Silk의 다양한 측면을 다룹니다. 발표자는 중첩된 실크 for 루프, 어셈블리 코드 생성, 리듀서를 사용한 축소, 스케줄러 및 성능 최적화와 같은 주제에 대해 논의합니다. 또한 각각 디버깅 및 확장성 분석을 위한 Silk Sanitizer 및 Silk Scale과 같은 관련 도구와 Silk 생태계에 대한 개요를 제공합니다. 요점은 멀티코어 프로세서를 위한 병렬 프로그램을 작성하는 것이 어려울 수 있지만 Silk는 복잡한 작업을 효율적으로 처리하여 프로세스를 단순화하여 프로그래머가 코드 실행을 더 잘 제어할 수 있도록 한다는 것입니다.
00:00:00 이 섹션에서 강사는 멀티 코어 프로그래밍과 멀티 코어 프로세서의 출현 이유에 대해 설명합니다. 칩에 들어갈 수 있는 트랜지스터의 수가 2년마다 2배로 증가한다는 무어의 법칙이 나타나고 2004년에서 2005년 사이에 클록 주파수 스케일링이 종료되면서 반도체 벤더들은 다중 프로세서 코어가 장착된 칩을 생산하기 시작했습니다. 이는 칩에서 단일 코어의 주파수를 더 이상 높일 수 없기 때문에 병렬 처리를 허용하는 설계 모델로 전환해야 했기 때문입니다. 강사는 또한 칩의 트랜지스터 수와 프로세서의 최대 주파수 사이의 관계를 명확히 합니다.
00:05:00 이 섹션에서 발표자는 클록 주파수를 높이면 전력 밀도가 기하급수적으로 증가하는 프로세서가 직면한 전력 밀도 문제에 대해 논의합니다. 이로 인해 무어의 법칙을 따르고 전력 밀도 제한을 초과하지 않기 위해 칩에 여러 개의 코어가 추가되었습니다. 그런 다음 연사는 칩 멀티프로세서로 알려진 추상적인 멀티코어 아키텍처를 소개하고 P 스레드, winAPI 스레드, 인텔 스레딩과 같은 다양한 동시성 플랫폼을 사용하여 멀티코어 머신에서 병렬 프로그램을 프로그래밍하기 위한 하드웨어 문제 및 소프트웨어 솔루션에 대한 강의를 설명합니다. 빌딩 블록, openmp 등.
00:10:00 이 섹션에서는 발표자가 멀티코어 프로그래밍에서 캐시가 작동하는 방식을 설명합니다. 한 프로세서가 주 메모리에서 캐시로 값을 로드하면 나중에 다시 액세스해야 하는 경우를 대비하여 해당 값을 캐시에 보관합니다. 다른 프로세서가 동일한 값을 로드하려는 경우 메인 메모리까지 가는 대신 첫 번째 프로세서의 캐시를 통해 가져올 수도 있습니다. 그러나 한 프로세서가 자체 캐시의 값을 업데이트하면 다른 프로세서의 캐시 값이 오래되어 문제가 발생합니다. MSI 프로토콜은 캐시 간의 일관성을 보장하기 위해 세 가지 가능한 상태(M, S 및 I)로 캐시 라인에 레이블을 지정하는 이 문제에 대한 기본 솔루션입니다.
00:15:00 이 섹션에서 강의는 공유 메모리 하드웨어에서 캐시 일관성 프로토콜의 기본 사항, 특히 한 프로세서 캐시의 캐시 라인에 대한 수정이 동일한 라인의 다른 캐시 사본을 무효화할 수 있는 방법에 대해 설명합니다. 강의에서는 간단한 프로토콜을 소개하고 다른 복잡한 프로토콜이 실제로 어떻게 존재하는지 설명합니다. 하드웨어는 여러 프로세서가 동일한 캐시 라인을 수정할 때 충돌을 관리할 책임이 있지만 이로 인해 "무효화 폭풍"이 발생하고 성능이 저하될 수 있습니다. 강의는 또한 동시성 플랫폼이 이러한 복잡성을 추상화하고 병렬 프로그래밍에서 동기화 및 통신을 도울 수 있다고 언급합니다.
00:20:00 이 섹션에서 발표자는 피보나치 수의 예를 사용하여 다양한 동시성 플랫폼에 대해 설명합니다. 피보나치 프로그램은 피보나치 수를 여러 번 계산하는 재귀 알고리즘을 사용하여 구현되므로 좋지 않은 알고리즘입니다. 두 개의 재귀 호출은 완전히 독립적인 계산이므로 병렬화할 수 있습니다. 스레딩을 위한 표준 API인 Pthreads를 사용하여 이 병렬화를 구현할 수 있습니다.
00:25:00 이 섹션에서 발표자는 프로그래밍에서 동시성을 가능하게 하는 함수 라이브러리인 Pthreads에 대해 설명합니다. Pthreads는 특별한 시맨틱이 포함된 함수 라이브러리를 사용하여 코드에서 동시성을 지정할 수 있는 DIY 동시성 플랫폼을 제공합니다. Pthreads의 각 스레드는 프로세서의 추상화를 구현하고 실제 시스템 리소스에 다중화됩니다. Pthreads는 또한 내부 스레드 조정과 관련된 프로토콜을 단순화하는 마스크를 제공합니다. Pthreads 라이브러리에는 pthread가 생성하는 새 스레드를 저장하고 식별하는 pthread_create 및 코드에서 계속 진행하기 전에 스레드가 완료될 때까지 대기하는 pthread_join과 같은 주요 기능이 있습니다. 연사는 Pthread를 사용하여 피보나치 수열을 구현하는 방법을 시연합니다.
00:30:00 이 섹션에서 발표자는 피보나치 수열을 병렬로 실행하기 위한 Pthreads 코드 구현에 대해 논의합니다. 입력 크기가 충분히 작으면 스레드를 병렬로 생성하는 비용 때문에 순차적으로 프로그램을 실행하는 것이 낫다고 설명한다. 코드는 입력 인수를 스레드에 마샬링하고 인수 구조에 저장합니다. 발표자는 Pthread 생성, Pthread 조인 및 코드가 스레드를 재귀적으로 생성해야 하는 경우 훨씬 더 복잡해지는 것과 같은 몇 가지 단점에 대해 설명합니다. 그들은 또한 이 코드가 하나의 스레드만 생성하므로 가능한 최대 속도 향상은 4개의 프로세서에서 실행되는 경우 2개라고 언급합니다.
00:35:00 비디오의 이 섹션에서는 Pthread의 문제와 피보나치 시퀀스 코드에 대해 설명합니다. 스레드 생성에 대한 높은 오버헤드로 인해 거친 동시성이 발생하고 확장성 문제는 두 코어가 동일한 양의 작업을 수행하지 않는다는 것입니다. 피보나치 논리가 하나의 함수 내에 잘 캡슐화되지 않아 유지 관리 및 변경이 어렵기 때문에 코드에는 모듈성이 부족합니다. 또한 어셈블리에서 코드를 작성해야 하는 것과 유사한 인수 마샬링으로 인해 코드가 복잡해집니다. 그런 다음 비디오에서는 이러한 문제에 대한 솔루션을 제공하기 위해 Intel에서 개발한 라이브러리인 TBB(Threading Building Blocks)를 소개합니다.
00:40:00 이 섹션에서는 프로그래머가 스레드를 직접 처리하지 않고도 네이티브 스레드와 작업 도용 알고리즘을 사용할 수 있도록 설계된 C++ 라이브러리인 Intel 스레드 빌딩 블록(TBB) 라이브러리의 사용에 대해 비디오에서 설명합니다. 작업을 지정함으로써 TBB는 작업을 스레드 간에 부하 분산하여 POSIX 스레드를 사용하는 것보다 코드를 더 간단하게 작성하고 수행할 수 있도록 합니다. 비디오는 TBB를 사용하여 피보나치 프로그램을 구현하는 예를 보여주며, 하위 작업을 재귀적으로 생성하여 여러 프로세서에서 더 많은 병렬성과 확장성을 허용하는 방법을 보여줍니다. 또한 TBB는 루프 병렬 처리, 데이터 집계 및 소프트웨어 파이프라인을 위한 템플릿과 공유 데이터에 대한 안전한 동시 액세스를 위한 동시 컨테이너 클래스를 제공합니다.
00:45:00 이 섹션에서 연사는 동시성 문제에 대한 두 가지 언어 솔루션인 OpenMP와 Silk를 소개합니다. OpenMP는 병렬로 실행해야 하는 코드 조각을 지정하기 위해 컴파일러 pragma를 사용하여 Fortran뿐만 아니라 C 및 C++에 대한 언어 확장을 제공하는 사양입니다. 루프 병렬 처리, 작업 병렬 처리 및 파이프라인 병렬 처리를 지원하고 많은 스케줄링 및 데이터 공유 지시문과 동기화 구성을 포함합니다. 발표자는 Pthread 또는 TBB를 사용하는 것보다 더 간단하고 더 나은 성능을 제공하는 OpenMP에서 피보나치를 구현하는 예를 제공합니다. OpenMP는 많은 기능을 제공하고 코드를 단순화하므로 병렬 프로그램 작성에 널리 사용되는 솔루션입니다.
00:50:00 이 섹션에서 발표자는 접합 및 벡터 병렬 처리를 지원하고 효율적인 작업 훔치기 스케줄러를 포함하는 실크 프로그래밍 플랫폼에 대해 설명합니다. 또한 이 프로그램에는 코드를 전역 변수와 병렬화하기 위한 하이퍼 개체 라이브러리가 있으며 실크 스크린 레이스 감지기 및 실크 뷰라는 확장성 분석기와 같은 프로그래밍 도구가 함께 제공됩니다. 발표자는 또한 수업에서 실크 플러스를 사용하지 않을 것이지만 테이퍼 LLVM으로 알려진 더 나은 컴파일러를 사용할 것이라고 언급했습니다. 이 컴파일러는 다른 모든 실크 구현보다 기본 컴파일러에 비해 더 나은 코드를 생성합니다.
00:55:00 이 섹션에서는 실크 스폰 및 실크 동기화 문을 사용하여 병렬 실행을 활성화하는 방법을 예제를 통해 설명합니다. 첫 번째 예는 n-1의 fib가 n-2의 fib가 실행되는 동안 이를 호출하는 함수와 병렬로 실행될 수 있음을 제안하는 silk spawn 및 silk sync 문을 포함하는 피보나치의 솔트 코트입니다. 그러나 런타임 시스템은 이러한 작업을 병렬로 실행할지 여부를 결정합니다. 논의된 또 다른 예는 반복 공간을 절반으로 재귀적으로 나누고 범위가 병렬로 실행하기에 너무 작아질 때까지 실크 생성 및 실크 동기화 문을 사용하는 컴파일러와 병렬로 for 루프를 실행하는 데 실크 for 문을 사용하는 루프 병렬 처리입니다. 올바른 결과를 위해 반복이 독립적임을 보장하는 것이 중요하며 실크를 사용하면 약간의 추가 오버헤드가 추가됩니다.
01:00:00 이 섹션에서는 비디오에서 중첩된 실크 for 루프를 사용하는 방법과 clang 컴파일러의 플래그를 사용하여 어셈블리 코드를 생성하는 방법에 대해 자세히 설명합니다. 실크 for 루프를 사용하여 값을 합산하는 예제 코드는 여러 프로세서가 동일한 메모리 위치에 쓸 때 결정 경쟁 문제를 제기합니다. Silk는 리듀서 매크로를 등록 및 등록 취소하는 동안 주어진 변수에 대한 추가 기능을 처리하는 하이퍼 객체인 리듀서를 사용하여 이 문제를 해결합니다. 이는 멀티코어 프로그래밍에서 발생할 수 있는 축소 문제를 다른 많은 축소 연산자와 함께 사용할 수 있는 방법으로 처리하는 방법입니다.
01:05:00 이 섹션에서 연사는 실크의 리듀서(연관 이진 연산 및 항등 요소가 있는 대수 구조)에 대해 설명합니다. Silk에는 더하기, 곱하기, 최소값, 최대값 및 XOR을 포함하여 미리 정의된 여러 리듀서가 있으며 고유한 리듀서를 정의할 수 있습니다. Silk의 이점 중 하나는 항상 프로그램의 유효한 직렬 해석이 있어 디버깅이 더 쉬워지고 작업 훔치기 스케줄링 알고리즘을 사용하여 프로그램을 모니터링하고 사용 가능한 프로세서 코어에 매핑하는 런타임 스케줄러가 있어 작업의 균형을 맞추는 것입니다. 고르게. 다른 동시성 플랫폼과 달리 Silk의 스케줄러는 이론적으로 효율적입니다.
01:10:00 이 섹션에서 연사는 Silk 소스 코드를 컴파일하는 방법, 병렬 및 직렬 성능 벤치마크, Silk Sanitizer 및 Silk와 같은 도구를 사용하여 문제를 디버그하는 방법을 포함하여 멀티코어 프로그래밍을 위한 Silk 에코시스템에 대한 높은 수준의 개요를 제공합니다. 규모. 또한 성능을 위해 직렬 프로그램을 최적화하는 것의 중요성과 Silk의 스케줄러가 프로그램 실행 중에 다양한 작업을 처리하는 방법을 강조합니다. 또한 연사는 실크 스케일이 코드가 활용할 수 있는 최대 프로세서 수를 결정하여 확장성을 분석하는 데 유용한 도구가 되는 방법을 설명합니다.
01:15:00 이 섹션에서는 연사가 멀티코어 프로그래밍 강의에서 얻은 핵심 내용을 요약합니다. 대부분의 최신 프로세서에는 다중 코어가 있어 고성능을 위해 병렬 프로그램을 작성해야 한다고 설명합니다. 그러나 그러한 프로그램을 작성하는 것은 어려울 수 있으며 여기에서 Silk가 사용됩니다. 이 도구는 프로그래머로부터 프로세서 코어를 추상화하고 동기화, 통신 프로토콜 및 로드 밸런싱을 처리합니다. 발표자는 또한 학생들이 Silk를 사용하여 자신의 병렬 스크린 세이버를 구현할 미래 프로젝트에 대해 언급합니다.
이 비디오는 Silk 프로그래밍의 경합, 병렬 처리 및 계산 dag와 관련된 다양한 주제를 다룹니다. 다루는 몇 가지 주요 개념에는 동시 실행을 위한 spawn 및 sync 문, 경합 조건 방지의 중요성 및 이를 식별하기 위한 Silk의 경합 감지기 사용이 포함됩니다. 이 비디오는 또한 작업 및 계산 범위를 분석하는 방법과 함께 프로그램에서 병렬 처리의 양을 정량화하는 방법으로 Amdahl의 법칙, 작업 법칙 및 범위 법칙을 다룹니다. 병렬 정렬 알고리즘의 잠재적인 속도 향상 및 병렬 처리와 스케줄링 이론의 개념도 탐욕스러운 스케줄러의 정리에 중점을 두고 논의됩니다. 전반적으로 비디오는 Silk 프로그래밍에서 프로그램 성능을 이해하고 최적화하는 데 유용한 통찰력을 제공합니다.
이 비디오는 T1/Tinfinity가 P^2보다 크거나 같은 한 모든 욕심쟁이 스케줄러가 거의 완벽한 선형 속도 향상을 달성한다고 기본적으로 명시하는 욕심쟁이 스케줄러 경계의 결과를 설명합니다. 작업 도용 스케줄러를 사용하는 실크 스케줄러는 프로세서 수가 T1/Tinfinity보다 훨씬 적은 한 거의 완벽에 가까운 선형 속도 향상을 달성할 수 있습니다. 실크 런타임 시스템은 준비된 가닥의 작업 데크를 유지 관리하여 작동하고 스택처럼 데크의 바닥을 조작합니다. 이 비디오는 또한 여러 스택 보기를 병렬로 허용하고 병렬 함수 호출을 가능하게 하는 Cactus Stack에 대해 설명합니다. P 프로세서 실행에 필요한 스택 공간의 상한선은 각 프로세서가 작업을 도용할 때마다 계산 그래프 아래로 완전히 내려갈 필요가 없기 때문에 필요한 실제 양보다 훨씬 느슨한 경우가 많습니다.
00:00:00 이 섹션에서 강사는 다가오는 숙제 및 프로젝트에 중요한 실크의 인종 및 병렬 처리 주제를 소개합니다. 부모 및 자식 기능의 동시 실행을 허용하는 Silk의 spawn 및 sync 문의 기본 사항을 검토합니다. 강사는 또한 MIT 정책 구성원과의 만남과 과거 사례에서 볼 수 있듯이 비참한 결과를 초래할 수 있는 코드의 경합 조건을 피하는 것의 중요성을 강조합니다. 찾기 가장 어려운 경주 버그는 치명적인 사건을 일으킨 버그이며 기존 테스트는 종종 효과적이지 않습니다. Silk는 코드에서 잠재적인 레이스 버그를 식별하는 데 도움이 되는 도구를 제공합니다.
00:05:00 이 섹션에서는 경주가 개발자가 발견하기 가장 어려운 버그 중 하나인 이유를 설명합니다. 논리적 병렬 코드가 동일한 메모리 위치에 액세스하고 적어도 하나의 쓰기를 등록하는 드문 경우에만 발생할 수 있기 때문입니다. 그것에. 예를 들어, 비디오는 종속성 그래프를 활용하여 두 개의 병렬 경로 간에 공유되는 레이스 버그가 항상 발생하는 것은 아님을 보여주는 간단한 코드를 보여줍니다. 경합은 두 저장소가 동일한 메모리 위치에 쓸 때 발생하며, 어떤 실행 경로가 완전히 먼저 실행되는지에 따라 다른 출력이 발생할 수 있습니다.
00:10:00 이 섹션에서 발표자는 두 개의 명령이 동일한 메모리 위치에 액세스하고 명령 중 적어도 하나가 쓰기 작업일 때 발생하는 결정 경쟁의 개념을 설명하여 프로그램에서 비결정적 동작을 초래합니다. 발표자는 Silk for-loop의 반복이 독립적인지 확인하고 Silk spawn 문과 해당하는 Silk sync 문 사이의 코드도 독립적인지 확인하는 등 경합을 피하는 방법에 대한 팁을 제공합니다. 발표자는 또한 기계어 크기가 중요하며 비표준 유형을 사용하는 압축 데이터 구조를 읽고 쓸 때 주의를 기울여야 한다고 지적합니다.
00:15:00 이 섹션에서는 프로그램에서 잠재적 경합 상태를 식별하는 데 도움이 되는 Silk 플랫폼의 "경합 감지기"에 대해 설명합니다. '-f sanitized equal to silk' 플래그를 사용하여 계측 프로그램을 생성함으로써 Silk는 문제가 되는 레이스를 보고하고 현지화할 수 있으므로 코드 디버그에 도움이 됩니다. 이 비디오는 또한 병렬 처리의 개념과 Silk 실행 모델이 계산 그래프를 사용하여 실행 중 계산 전개를 설명하는 방법을 설명합니다. 프로그램 성능을 최적화하고 개선하려고 할 때 이러한 개념을 이해하는 것이 중요합니다.
00:20:00 계산 dag의 정점 유형: 초기 가닥, 연속 가닥, 함수 호출 가닥 및 최종 가닥. 초기 스트랜드에는 실행될 첫 번째 명령이 포함되고 마지막 스트랜드에는 프로그램에서 실행되는 마지막 명령이 포함됩니다. 연속 가닥은 생성 작업의 연속을 나타내는 반면 함수 호출 가닥은 함수 호출의 실행을 나타냅니다. 계산 dag는 실행 중에 동적으로 전개되며 프로세서를 인식하지 못합니다. 즉, 런타임 시스템은 런타임에 작업을 프로세서에 매핑하는 방법을 알아냅니다. 요약하면, 계산 dag는 프로그램의 병렬성과 동시성을 이해하는 강력한 도구입니다.
00:25:00 이 섹션에서는 계산 dag와 프로그램에서 병렬 처리를 분석하는 데 사용할 수 있는 방법에 대해 알아봅니다. 계산 dag는 프로그램의 다른 부분 간의 종속성을 나타내며 스폰 에지, 호출 에지, 리턴 에지 및 계속 에지를 포함하여 다양한 유형의 에지를 가집니다. 계산 dag를 사용하여 프로그램에 얼마나 많은 병렬성이 있는지 분석할 수 있으며 Amdahl의 법칙을 사용하여 병렬성의 양을 정량화합니다. 제공된 예제에는 순차적으로 실행해야 하는 노드가 7개 미만이며 이는 계산에 어느 정도의 병렬 처리가 있음을 나타냅니다.
00:30:00 이 섹션에서는 병렬 처리에서 가능한 최대 속도 향상을 결정하는 방법으로 Amdahl의 법칙 개념을 소개합니다. 프로그램의 직렬 부분은 3/18로 결정되어 최대 속도 향상은 6입니다. Amdahl의 법칙은 병렬 처리에 대한 상한을 제공하지만 실제 사례에서는 종종 너무 느슨합니다. 작업법과 스팬법은 병렬 처리의 대안적 정의로 소개되며, 작업법은 P 프로세서의 실행 시간이 P로 나눈 프로그램의 작업보다 크거나 같다고 명시하고 스팬법은 실행 시간이 on P processors는 최소한 무한한 수의 프로세서에서 실행 시간입니다. 이러한 법칙은 대부분의 경우 Amdahl의 법칙보다 최대 속도 향상에 대한 더 나은 상한선을 제공합니다.
00:35:00 이 섹션에서 화자는 작업을 구성하는 방법과 다양한 계산의 양에 대해 설명합니다. 그들은 두 개의 병렬 계산을 실행할 때 작업은 여전히 개별 계산 작업의 합계이며 스팬은 개별 계산 스팬의 최대값이라고 설명합니다. 발표자는 또한 P 프로세서의 속도 향상을 정의하고 하위 선형, 선형 및 초선형 속도 향상에 대해 설명합니다. 그들은 가능한 최대 속도 향상이 계산의 병렬성과 동일하며, 이는 계산을 따라 단계당 평균 작업량과 같다는 점에 주목합니다. 전반적으로 이 섹션에서는 계산의 구성과 병렬 처리를 측정하는 방법에 대한 통찰력을 제공합니다.
00:40:00 이 섹션에서 발표자는 계산 DAG 및 병렬 퀵 정렬 알고리즘과 같은 예를 사용하여 최대 병렬도를 계산하기 위해 작업 및 계산 범위를 분석하는 방법에 대해 설명합니다. 연사는 컴파일러 계측을 사용하여 프로그램의 직렬 실행을 분석하고 프로그램의 병렬 속도 향상에 대한 상한선을 도출하는 실크 스케일 확장성 분석기를 소개합니다. 발표자는 또한 대규모 계산의 병렬 처리를 손으로 분석하는 것은 지루할 수 있지만 Silk Scale이 도움이 될 수 있다고 언급합니다.
00:45:00 이 섹션에서 비디오는 병렬 계산을 실행하고 관찰된 속도 향상과 범위 및 작업 법칙의 범위를 보여주는 플롯을 생성한 결과에 대해 설명합니다. 플롯은 최대 속도 향상이 약 5임을 보여주며 프로그램의 병렬 처리가 낮음을 나타냅니다. 분석 결과 병렬 처리에 대한 병목 현상은 파티션 기능을 순차적으로 실행하고 있으며 병렬 버전의 퀵 정렬의 예상 작업 및 범위는 n log n 정도입니다. 달성할 수 있는 최대 병렬 처리는 log log n 정도이며 그다지 높지 않습니다. 병렬성을 높이려면 분할 함수를 병렬화해야 합니다.
00:50:00 이 섹션에서 연사는 상당한 속도 향상을 위해 파티션 및 병합 정렬 알고리즘에서 병렬 처리를 구현하는 것의 중요성에 대해 논의합니다. 이러한 알고리즘의 병렬 버전에는 로그 제곱 n과 n 오버 로그 n의 높은 병렬 처리로 바인딩된 전체 범위가 있습니다. 또한 병렬 처리가 높고 해당 순차 알고리즘과 점근적으로 동일한 작업을 수행하는 다른 실용적인 병렬 알고리즘이 많이 있습니다. 발표자는 또한 스케줄링 이론의 개념을 소개하면서 중앙 집중식 스케줄러가 실행 시간에 계산 DAG를 사용 가능한 프로세서에 매핑할 수 있는 반면 분산 스케줄러는 Silk 프로그래밍에 사용된다고 설명합니다. 계산의 모든 단계에서 가능한 한 많은 작업을 수행하는 그리디 스케줄러가 예로 사용됩니다.
00:55:00 이 섹션에서는 미래에 대해 생각하지 않고 현재 시간 단계에서 가능한 한 많은 작업을 수행하는 욕심 많은 스케줄러의 개념을 소개합니다. 적어도 P 가닥이 준비된 완전한 단계와 P 가닥보다 적은 가닥이 준비된 불완전한 단계가 정의됩니다. 1968년 Ron Graham이 처음으로 제시한 유명한 정리는 탐욕스러운 스케줄러에 의해 달성된 시간 제한이 T1/P + T 무한대보다 작거나 같다는 것입니다. 여기서 T1은 작업이고 T 무한대는 범위입니다. 이 정리에 대한 증명이 제공되며 욕심 많은 스케줄러가 최적 실행 시간의 2배 이내에서 달성하는 것으로 나타났습니다.
01:00:00 이 섹션에서 비디오는 최적 스케줄러의 2배 이내에서 달성하는 욕심 많은 스케줄러 경계의 결과를 설명합니다. 그 결과 T1/Tinfinity가 P^2보다 크거나 같을 때 탐욕스러운 스케줄러는 거의 완벽한 선형 속도 향상을 달성합니다. 여기서 T1/P 곱하기 T infinity는 프로세서 수와 비교하여 계산에서 병렬 처리의 양을 측정합니다. 사용 가능. 실크 스케줄러는 T1/P + 차수 T 무한대와 동일한 TP의 예상 실행 시간을 갖는 작업 도용 스케줄러를 사용하며 스케줄링의 오버헤드를 설명하기 위해 T 무한대 앞에 Big O가 있고 거의 다음을 달성할 수 있습니다. 프로세서 수가 T1/Tinfinity보다 훨씬 적은 한 완벽한 선형 속도 향상. 실크 런타임 시스템은 준비된 가닥의 작업 데크를 유지 관리하여 작동하고 스택처럼 데크의 바닥을 조작합니다. 실크 스케일의 계측을 통해 작업 및 스팬 용어를 측정하여 프로그램의 병렬성을 결정할 수 있습니다.
01:05:00 이 섹션에서 발표자는 프로세서의 생성 및 병렬 처리 개념에 대해 설명합니다. 그들은 프로세서가 함수를 호출할 때 해당 함수의 프레임을 스택 맨 아래에 놓고 스택 맨 아래에서 프레임을 생성할 수 있다고 설명합니다. 여러 프로세스가 병렬로 발생할 수 있으며 생성 및 호출에서 반환할 수 있습니다. 작업자가 할 일이 없어지면 다른 프로세서의 데크 상단에서 훔칩니다. 유명한 정리에 따르면 작업자는 도둑질을 매우 드물게 하여 거의 선형에 가까운 속도 향상을 제공합니다. 발표자는 또한 Silk가 스택 공간에 대한 포인터를 부모에서 자식으로 전달할 수 있지만 자식에서 부모로 전달할 수 없는 포인터에 대한 C 규칙을 지원한다고 언급합니다.
01:10:00 비디오의 이 섹션에서 연사는 실크 프로그램의 조상 계산 그래프에서 작업으로 볼 수 있는 스택인 Cactus 스택에 대해 설명합니다. 이 스택은 스택의 다중 보기를 병렬로 허용하므로 병렬 함수 호출이 가능합니다. 발표자는 Silk 프로그램에 필요한 스택 공간은 프로그램의 직렬 실행에 필요한 스택 공간(S sub 1)에 사용할 프로세서 수(P)를 곱하여 구할 수 있다고 설명합니다(S 하위 P ≤ P x S 하위 1). 발표자는 이 개념에 대한 높은 수준의 증거를 제공하고 P 프로세서 실행에 필요한 스택 공간의 상한은 종종 각 프로세서가 계산 그래프를 끝까지 내려갈 필요가 없기 때문에 필요한 실제 양보다 훨씬 더 느슨하다는 점에 주목합니다. 일을 훔치는 시간.
이 비디오는 나누기 및 정복 반복을 분석하기 위한 마스터 방법에 대해 설명하고 n의 증가와 필요한 작업을 결정하기 위해 n의 로그 밑 B와 A의 로그 밑 B를 N의 F와 비교하여 멀티스레드 알고리즘에 적용합니다. 이 비디오는 기본 멀티스레드 알고리즘에 대한 솔루션이 포함된 치트 시트를 제시하고 작업 및 범위 분석, 작업 효율성, 입자 크기 최적화를 통한 오버헤드 비용 극복과 같은 주제를 다룹니다. 기술적인 주제를 전달할 때 공감의 중요성이 강조되고, 병렬 처리를 높이고 실행 시간을 줄이기 위해 작업과 범위의 균형을 맞추는 수단으로 DAG 개념이 도입됩니다.
이 비디오는 작업 및 스팬에 초점을 맞춘 멀티스레드 알고리즘 분석과 스팬을 최소화하면서 병렬 처리를 최대화하여 거의 완벽한 선형 속도 향상을 달성하는 방법에 대해서도 설명합니다. 발표자는 스레드에 할당된 작업 수가 충분히 많은 다중 스레드 알고리즘에 대한 분할 및 정복 접근 방식을 제안하고 스케줄링 오버헤드로 인해 수많은 작은 작업을 생성하지 않도록 경고합니다. 제시된 예제 코드에는 효율적인 코드와 형편없는 코드가 포함되어 있습니다. 연사는 또한 2차원 코딩 및 인덱싱에서 부분 행렬을 표현하는 방법에 대해 논의하고 분할 및 정복 행렬 곱셈 코드에서 '제한'을 사용하여 성능을 향상시키는 방법을 강조합니다.
00:00:00 이 섹션에서 강사는 학생들에게 분할 정복 반복과 이를 해결하는 일반적인 방법인 마스터 방법에 대해 상기시키는 것으로 시작합니다. 이 방법은 반복과 그 형식을 처리합니다. T(n) = a*T(n/B) + F(n), 여기서 a는 상수, B는 분할 계수, F(n)은 총 작업량입니다. 문제를 크기 n/B의 하위 문제로 분할합니다. 학생들은 재귀 트리와 각 수준이 어떻게 n/B 크기의 하위 문제로 나뉘는지, 행 전체에 실행 시간을 더하고, 트리의 높이를 계산하고 각 수준의 하위 문제 수를 곱합니다(a ^케이). 마지막으로 학생들은 A의 n^log base B가 알고리즘의 총 실행 시간임을 계산합니다.
00:05:00 이 섹션에서 발표자는 멀티스레드 알고리즘을 평가할 때 n의 성장과 필요한 작업을 결정하는 방법을 설명합니다. 핵심은 n의 로그 밑 B를 A의 로그 밑 B와 N의 F와 비교하는 것입니다. 화자는 세 가지 가능한 경우를 다룹니다. 첫 번째는 로그 밑 B n이 n의 F보다 훨씬 클 때입니다. 이 경우 가중치의 일정한 비율은 리프에 있으므로 답은 A의 로그 밑수 B에 대한 n이 됩니다. 두 번째 경우는 로그 밑수 Bn이 n의 F와 거의 같은 경우입니다. 이를 위해 추가 로그를 추가하고 답은 로그의 로그 밑수 B에 대한 n과 n의 k 더하기 1입니다. 마지막으로, 세 번째 경우는 로그 밑수 B가 N의 F보다 훨씬 작은 경우입니다. 즉, F는 규칙성 조건을 충족해야 하며, 이는 다항식 및 로그처럼 보게 될 모든 함수에 의해 충족됩니다.
00:10:00 이 섹션에서 발표자는 컴퓨터 과학에서 일반적으로 사용되는 기본 다중 스레드 알고리즘 솔루션이 포함된 치트 시트를 제시합니다. 첫 번째 알고리즘인 T(n) = T(n/2) + n은 케이스 1에 해당하므로 Θ(n^2)의 해를 가집니다. 두 번째 알고리즘인 T(n) = T(n/2) + n^2logn은 k = 0인 경우 2에 속하므로 Θ(n^2logn)의 솔루션을 갖습니다. 세 번째 알고리즘의 경우 T(n) = T(n/2) + n^2, 경우 1에 해당하므로 솔루션은 Θ(n^2)입니다. 네 번째 알고리즘인 T(n) = 2T(n/2) - n은 마스터 방법의 어떤 경우에도 속하지 않고 해가 Θ(n^2loglogn)이므로 까다롭습니다.
00:15:00 이 섹션에서 발표자는 Aqua Bazi 방법과 대부분의 프로그램을 분석하기에 충분한 마스터 방법보다 더 복잡한 방법에 대해 설명합니다. 그런 다음 외부 루프가 병렬화되는 제자리 행렬 전치 코드가 있는 병렬 루프의 예를 제공합니다. 발표자는 효율적인 병렬 처리를 위해 반복 공간과 로드 밸런싱을 올바르게 정의하는 것의 중요성을 강조합니다. 또한 개방형 실크 컴파일러 및 런타임 시스템에서 루프를 구현하는 방법도 설명합니다.
00:20:00 이 섹션에서 발표자는 분할 및 정복을 활용하여 루프를 두 부분으로 분할하고 하나의 요소 반복에 도달할 때까지 양쪽에서 자신을 재귀적으로 호출하는 루프에 대한 재귀 프로그램을 설명합니다. 이 계산 작업은 작업과 범위 측면에서 분석되며 리프 작업은 차수 n 제곱이고 상단 부분은 리프에서 루트까지 모든 수준에 n개의 노드가 있기 때문에 세타 n입니다. 개방형 실크 런타임 시스템에는 루프 프리미티브가 없으므로 루프는 이 병렬 분할 및 정복 접근 방식으로 효과적으로 변환됩니다.
00:25:00 이 섹션에서 발표자는 다중 스레드 알고리즘의 작업 및 범위 분석에 대해 설명합니다. 그는 완전한 이진 트리의 n개 잎 각각에 대해 일정한 작업이 수행되기 때문에 총 작업은 Θ(n²)라고 설명합니다. 루프 제어 범위는 log(n)이며, 이는 무한한 수의 프로세서가 대수 시간 내에 작업을 완료할 수 있음을 의미합니다. 그러나 계산(n)에 대한 선형 구성 요소가 있으므로 총 스팬은 Θ(n)입니다. 따라서 병렬 처리는 Θ(n)이며 이는 대부분의 실제 시스템에 적합한 양입니다. 그런 다음 연사는 내부 루프도 병렬화되는 시나리오를 탐색하고 결과 작업량에 대해 논의합니다.
00:30:00 비디오의 이 섹션에서 교수는 병렬 알고리즘에서 작업 효율성의 개념에 대해 설명합니다. 병렬화 알고리즘은 작업을 변경하지 않지만 큰 병렬화를 달성하기 위해 계산 범위를 줄여야 합니다. 그러나 때로는 병렬화로 인해 더 많은 작업이 추가될 수 있으며, 이는 원래 알고리즘에 비해 프로그램 속도를 늦추기 때문에 문제가 될 수 있습니다. 작업 효율적인 병렬 알고리즘은 더 많은 작업을 추가하지 않고 큰 병렬 처리를 달성하기 위해 스팬을 줄일 수 있기 때문에 교수가 가르치는 데 관심이 있는 것입니다. 교수는 학습 과정에서 질문하고 실수하는 것의 중요성을 강조합니다. 같은 질문을 가지고 있지만 질문하기를 두려워하는 다른 사람들을 도울 수 있기 때문입니다. 그는 학생들이 상위 10%에 속하지 않더라도 학습 과정에 참여하고 참여할 것을 권장합니다.
00:35:00 이 섹션에서는 기술적인 주제와 관련하여 커뮤니케이션에서 공감의 중요성을 강조합니다. 교수는 학생들이 다루는 자료에 익숙하지 않을 수 있는 학급의 다른 사람들에 대해 인내심을 갖도록 격려합니다. 다중 스레드 알고리즘의 분석으로 이동하여 벡터 추가를 위한 분할 정복 알고리즘이 제시되며 병렬 처리는 n 나누기 log n인 것으로 확인됩니다. 병렬 처리와 프로세서 수 사이의 관계에 대해 논의하며 교수는 병렬 처리가 많을수록 더 좋아 보일 수 있지만 특정 임계값까지만 이점이 있다고 강조합니다.
00:40:00 이 섹션에서 발표자는 멀티스레드 알고리즘의 일부 오버헤드, 특히 서브루틴 호출 오버헤드를 최적화하는 방법에 대해 설명합니다. 분할 정복 프로세스의 리프에서 청크당 최대 G개의 요소가 있음을 컴파일러에 제안하는 "입자 크기" 개념을 도입합니다. 이를 통해 서브루틴 오버헤드가 한 번이 아닌 G 반복에 걸쳐 상각되어 성능이 향상됩니다. 입자 크기가 지정되지 않은 경우 시스템은 오버헤드를 최소화하기 위해 최선의 추측을 합니다. 화자는 변수 I, G 및 s를 분해하여 이 컨텍스트에서 작업을 분석하고 병렬 제어 항목이 없는 원래 코드의 작업과 비교합니다.
00:45:00 이 섹션에서 발표자는 멀티스레드 알고리즘을 분석하는 방법과 최신 비순차 프로세서에서 루프 제어가 저렴한 방법에 대해 이야기합니다. 그들은 무한한 수의 프로세서로 알고리즘을 실행하는 데 걸리는 시간인 스팬을 살펴보고 오버헤드 비용과 반복 비용을 논의합니다. 화자는 잎의 수와 각각에 대해 수행해야 하는 's'라고 하는 다채로운 작업 측면에서 범위를 세분화합니다. 또한 완전한 이진 트리의 내부 노드 수와 범위를 계산하는 데 사용되는 경로에 대한 질문에 답합니다.
00:50:00 이 섹션에서 발표자는 다중 스레드 알고리즘의 분석, 특히 DAG(Directed Acyclic Graph)의 개념과 이것이 알고리즘의 경로에 미치는 영향에 대해 논의합니다. 병렬 처리를 허용하기 위해 DAG의 서로 다른 하위 트리 간의 독립성이 필요함을 강조합니다. 이 두 가지 요소가 반대 방향으로 작동하므로 목표는 알고리즘의 작업과 범위의 균형을 맞추는 것입니다. 핵심은 G(병렬 처리량)가 s over I(알고리즘의 순차적 부분)보다 훨씬 커 오버헤드가 적고 처리 속도가 빨라지는 것입니다. 발표자는 또한 이 개념의 구현에 대해 언급하지만 나중에 강의 시리즈에서 논의할 것임을 언급합니다.
00:55:00 이 섹션에서 연사는 for 루프를 사용하여 두 벡터를 더하는 다중 스레드 알고리즘 구현을 제시합니다. 루프는 직렬 벡터 덧셈을 수행하기 위해 V add라는 연산자를 사용하고, 루프는 크기 G의 벡터를 사용하여 G 그룹에 덧셈을 생성합니다. G가 1이라고 가정하면 루프 작업은 차수 n이며 범위도 다음과 같습니다. 주문 n. 병렬도는 스팬에 대한 작업의 비율을 n으로 나누어 1로 단순화하여 측정합니다. 발표자는 멀티스레딩 알고리즘 분석의 목표가 병렬성을 높이고 스팬을 줄여 런타임을 최소화하는 것이라고 강조하고 기술을 강조합니다. 다중 스레드 알고리즘을 개선하는 한 가지 방법으로 계산을 병렬화하기 위해 길이 N의 루프가 이중 중첩 루프로 대체되는 스트립 마이닝이라고 합니다.
01:00:00 이 섹션에서 발표자는 멀티스레드 알고리즘의 성능을 작업과 스팬 측면에서 분석합니다. 스팬이 분모에 있기 때문에 스팬을 최소화하여 병렬성을 최대화하는 방법에 대해 설명합니다. 핵심은 거의 완벽한 선형 속도 향상을 원하는 경우 프로세서보다 10배 더 많은 병렬 처리를 생성하는 것입니다. 발표자는 또한 필요한 경우 작업 오버헤드를 줄이기 위해 일부 병렬 처리를 교환할 것을 제안합니다. 그들은 충분한 평행성이 유지되는 한 입자 크기를 만지작거리도록 권장합니다.
01:05:00 이 섹션에서 발표자는 다중 스레드 알고리즘에서 분할 정복 전략을 사용하는 방법에 대해 논의하고 여러 개의 작은 작업을 차례로 생성하지 말라고 조언합니다. 괜찮습니다. 일반적으로 스레드에 할당된 작업 수가 충분히 많은 분할 정복 접근 방식이 있어야 합니다. 발표자는 일정 오버헤드를 조심하라고 경고하고 더 많은 오버헤드가 있는 내부 루프 대신 외부 루프를 병렬화할 것을 제안합니다. 여기에 제시된 예제 코드는 스케줄링이 한 번만 발생하는 효율적인 코드와 오버헤드가 n번 발생하는 형편없는 코드를 보여줍니다. 행렬 곱셈은 2 행렬에 대해 n 나누기 2 곱하기 n 의 8 곱셈을 수행한 다음 2 n x n 행렬을 더함으로써 n 곱하기 n 행렬을 곱하기 위해 분할 및 정복 전략을 사용하는 다중 스레드 알고리즘의 예로 사용됩니다.
01:10:00 이 섹션에서 발표자는 특히 C 및 Fortran과 같은 언어의 행 주요 순서 및 열 주요 순서에서 2차원 코딩 및 인덱싱에서 하위 행렬을 나타내는 방법에 대해 논의합니다. 아이디어는 모든 2차원 행렬을 1차원 행렬로 인덱싱할 수 있고 하위 행렬을 다룰 때 긴 행렬의 행 수와 길이를 추가하여 IJ 요소가 어디에 있는지 알 수 있다는 것입니다. 또한 분할 정복을 구현할 때 4개의 하위 행렬 각각의 시작 모서리를 아는 것이 중요합니다. 궁극적으로 발표자는 분할 및 정복 행렬 곱셈 코드에서 '제한'을 사용하여 어떤 요소를 앨리어싱할 수 있는지 또는 할 수 없는지 컴파일러에 알리는 것을 강조합니다.
01:15:00 이 섹션에서 발표자는 행렬 곱셈을 위한 다중 스레드 알고리즘에 대해 설명합니다. 이 알고리즘은 행렬을 더 작은 부분 행렬로 재귀적으로 세분화하는 것을 기반으로 하며 각 부분 행렬은 재귀적으로 곱하여 최종 결과를 얻습니다. 발표자는 n이 2의 거듭제곱인지 여부를 빠르게 결정하기 위한 비트 트릭을 강조하고 매크로를 사용하여 행렬의 인덱싱을 단순화합니다. 알고리즘은 성능 향상을 위해 줄일 수 있는 높은 병렬 처리를 나타냅니다. 다른 유사한 알고리즘도 언급됩니다.
이 비디오는 다양한 예제를 사용하여 컴파일러가 코드를 최적화하는 방법에 대해 설명합니다. 컴파일러가 불필요한 스토리지 및 메모리 참조를 제거하는 방법과 루프를 최적화하여 성능을 향상시키는 방법에 대해 설명합니다.
이 비디오는 또한 컴파일러 최적화 단계의 개념과 이를 사용하여 코드 성능을 개선하는 방법에 대해서도 설명합니다. 또한 특히 벡터화와 관련하여 컴파일러의 제한 사항에 대해서도 설명합니다. 컴파일러는 코드의 포인터가 앨리어스되지 않는다는 것을 확인할 수 있는 경우에만 코드를 벡터화할 수 있습니다. 포인터가 별칭을 지정하면 컴파일러는 코드를 벡터화할 수 없습니다. 프로그래머는 포인터 사용에 대한 자세한 정보를 제공하도록 포인터에 주석을 달아 컴파일러를 도울 수 있습니다.
00:00:00 이 강의에서 Tao Schardl은 컴파일러가 할 수 있는 것과 할 수 없는 것에 대해 논의합니다. 그는 컴파일러 최적화를 연구하면 개발자가 최적화를 활용하는 코드를 작성하는 방법과 컴파일러가 이미 최적화할 수 있는 코드를 수동으로 최적화하지 않는 방법을 이해하는 데 도움이 될 수 있다고 설명합니다.
00:05:00 컴파일러는 큰 소프트웨어이며 컴파일러 자체에 버그가 있을 때 디버깅에 절대적으로 도움이 될 수 있습니다. 컴파일러가 어디에서 실수를 저질렀는지 또는 컴파일러가 수행할 수 있어야 한다고 생각한 작업을 수행하지 않은 위치를 이해하는 데 도움이 됩니다.
00:10:00 컴파일러는 많은 최적화를 수행할 수 있지만 수행할 수 없는 작업이 있습니다. 예를 들어 항상 빠른 경로를 생성하거나 루프를 최적화할 수는 없습니다.
00:15:00 컴파일러는 코드를 최적화하기 위해 많은 일을 할 수 있지만 제대로 할 수 없는 일도 있습니다. 한 가지 예는 데이터 구조입니다. 컴파일러는 함수와 같은 방식으로 데이터 구조에 대해 똑똑하지 않습니다. 다른 하나는 루프입니다. 컴파일러가 일부 최적화를 수행할 수 있지만 제한이 있습니다.
00:20:00 이 YouTube 비디오는 컴파일러가 간단한 작업을 사용하여 더 복잡한 작업을 대체하는 방법을 설명합니다. 예를 들어 나누기 연산을 대체하기 위해 컴파일러는 매직 넘버를 곱한 다음 결과를 이동할 수 있습니다. 이 비디오는 또한 주소 계산기가 어떻게 작동하는지 설명합니다.
00:25:00 이 비디오는 간단한 "vex 스케일" 함수를 예로 들어 컴파일러가 코드를 최적화하는 방법에 대해 설명합니다. 코드는 먼저 최적화 없이 표시되고 다양한 최적화가 적용된 상태로 표시됩니다. 표시된 최적화에는 명령어 수 감소, 벡터 명령어 사용 및 매직 넘버 사용이 포함됩니다.
00:30:00 이 비디오는 컴파일러가 불필요한 메모리 작업을 제거하여 코드를 최적화하는 방법에 대해 설명합니다. 특히 메모리에 값을 저장할 필요가 없도록 컴파일러가 두 스칼라 값을 곱하는 함수를 최적화하는 방법을 보여줍니다. 마지막으로 컴파일러가 구조를 메모리에 저장할 필요가 없도록 하여 구조에서 작동하는 함수를 최적화할 수 있는 방법을 보여줍니다.
00:35:00 이 YouTube 동영상에서 발표자는 컴파일러가 불필요한 저장소 및 메모리 참조를 제거하여 코드를 최적화하는 방법을 설명합니다. 그는 여러 필드가 있는 구조의 예를 사용하고 컴파일러가 주소 계산과 관련된 수학을 주의 깊게 분석하여 코드를 최적화하는 방법을 보여줍니다. 각 명령이 수행하는 작업을 이해함으로써 컴파일러는 코드를 최적화하고 불필요한 작업을 제거할 수 있습니다.
00:40:00 컴파일러는 데이터 구조와 스칼라 값을 변환하여 순전히 레지스터 내에 가능한 한 많이 저장하고 가능한 경우 로컬 저장소를 사용하지 않도록 노력합니다. 함수 호출의 경우 컴파일러는 호출 명령과 호출 중인 함수의 코드를 확인합니다. 그런 다음 위 코드의 기능을 더 빠르게 만들려고 시도합니다.
00:45:00 컴파일러는 함수 호출 오버헤드를 방지하기 위해 코드를 인라인할 수 있으며 불필요한 작업을 제거하여 코드를 최적화할 수도 있습니다.
00:50:00 이 YouTube 비디오에서 발표자는 컴파일러가 함수를 인라인하지 않는 세 가지 주요 이유가 있다고 설명합니다. 코드 크기 및 손상 성능. 발표자는 또한 자신의 프로그램에서 함수 인라인을 제어하기 위한 몇 가지 팁을 제공합니다.
00:55:00 이 비디오는 컴파일러가 루프를 최적화하여 프로그램을 더 빠르게 실행할 수 있는 방법을 보여줍니다. 코드 호이스팅 또는 루프 불변 코드 모션은 성능을 개선하는 데 사용할 수 있는 최적화 중 하나입니다.
01:00:00 컴파일러는 일련의 변환 패스를 수행하여 코드를 최적화할 수 있습니다. 이러한 패스는 동일한 주소 계산과 같은 속성을 찾아 보다 효율적인 코드로 대체하도록 설계되었습니다.
01:05:00 컴파일러는 'x'와 'y'의 주소가 겹치는지 여부를 알지 못함에도 불구하고 이 루프를 벡터화할 수 있습니다. 입력으로 주어진 두 줄짜리 함수보다 컴파일된 코드의 구조가 더 복잡하기 때문이다.
01:10:00 이 YouTube 동영상은 컴파일러가 할 수 있는 것과 할 수 없는 것을 설명합니다. 코드에 루프가 포함되어 있지 않으면 컴파일러는 코드를 벡터화할 수 있습니다. 그러나 코드에 루프가 포함된 경우 컴파일러는 루프가 벡터 연산으로 가득 찬 경우에만 코드를 벡터화할 수 있습니다. 루프가 벡터 연산으로 가득 차 있지 않으면 컴파일러는 코드를 벡터화할 수 없습니다.
01:15:00 컴파일러가 코드를 벡터화할 수 있는지 여부에 대한 질문은 여러 요인에 따라 달라지므로 어려운 질문입니다. 특히 컴파일러는 두 개의 포인터가 별칭을 만들지 여부를 결정할 수 있어야 하는데 이는 어려운 작업이 될 수 있습니다. 프로그래머는 포인터 사용에 대한 자세한 정보를 제공하도록 포인터에 주석을 달아 컴파일러를 도울 수 있습니다.
강의 36: Alan Edelman과 Julia Language
강의 36: Alan Edelman과 Julia Language
이 비디오에서 Alan Edelman은 기계 학습을 위한 프로그래밍 언어의 힘과 수학에서의 중요성에 대해 설명합니다. 그는 기술적 장점과 기계 학습에서의 유용성으로 인해 Google에서 인정한 Julia 언어의 최근 개발을 강조합니다. Edelman은 Julia의 자동 미분 작동 방식을 설명하고 Babylonian 알고리즘을 통해 수치적 유한 차이를 사용하지 않고 x의 제곱근을 계산하는 예를 제공합니다. 또한 효율적인 계산을 위해 Julia에서 유형을 사용하고 블록 행렬을 사용하여 역전파 프로세스를 단순화하는 방법에 대해서도 설명합니다. 전반적으로 Edelman은 수학적 계산을 위한 선형 대수학의 중요성과 복잡한 현상을 이해하는 역할을 강조합니다.
MIT 6.172 소프트웨어 시스템의 성능 공학, 2018년 가을 - 1. 소개 및 행렬 곱셈
1. 소개 및 행렬 곱셈
"1. 소개 및 행렬 곱셈"이라는 제목의 이 YouTube 동영상에서 강사는 성능 공학의 중요성과 시간이 지남에 따라 어떻게 발전해 왔는지에 대해 설명합니다. 연사는 매트릭스 곱셈의 예를 사용하여 코딩 기술과 기계 사양이 성능에 얼마나 큰 영향을 미칠 수 있는지 보여줍니다. 토론에서는 루프 순서, 캐시 사용 및 병렬 프로그래밍과 같은 주제를 다룹니다. 발표자는 또한 다양한 프로세서 및 산술 계산을 위해 코드를 최적화하는 방법을 탐색합니다. 전반적으로 비디오는 성능 공학의 세계와 최신 컴퓨팅 시스템에서의 실용적인 응용 프로그램에 대한 귀중한 통찰력을 제공합니다.
강의 2. 작업 최적화를 위한 Bentley 규칙
2. 작업 최적화를 위한 Bentley 규칙
이 YouTube 비디오는 컴퓨터 프로그램을 위한 다양한 최적화 기술에 대해 설명합니다. 작업 최적화를 위한 Bentley 규칙이 도입되고 최적화가 데이터 구조, 루프, 논리 및 기능으로 그룹화됩니다. 값 인코딩, 데이터 구조 확장, 사전 계산, 캐싱 및 희소 행렬 활용과 같은 다양한 기술에 대해 설명합니다. 연사는 또한 그래픽 프로그램에서 그래프, 논리 최적화 및 충돌 감지 최적화를 위한 희소 행렬 표현 사용의 이점에 대해 설명합니다. 이러한 최적화 기술을 구현하면 프로그램의 실행 시간을 줄이고 효율성을 높일 수 있습니다.
비디오의 두 번째 부분에서는 루프 호이스팅, 루프에서 센티넬 사용, 루프 언롤링 및 퓨전, 함수 인라인을 비롯한 여러 범주의 최적화 기술을 다룹니다. 발표자는 조기 최적화에 대해 조언하고 정확성 유지 및 회귀 테스트 사용의 중요성을 강조합니다. 이 비디오는 또한 효율적인 방식으로 생산성을 높이고 목표를 달성하기 위한 6단계 가이드인 작업 최적화를 위한 Bentley 규칙을 간략하게 설명합니다. 이러한 규칙에는 명확한 목표 설정, 작업 세분화, 계획 및 구성, 작업 우선 순위 지정, 산만 최소화, 정기적인 접근 방식 검토 및 조정이 포함됩니다.
강의 3. 비트핵
3. 비트 해킹
이 YouTube 비디오는 이진 표현, 2의 보수, 비트 연산자, 임시 변수 없이 변수 교환, 코드 최적화를 비롯한 다양한 비트 조작 주제를 다룹니다. 이 비디오는 if-else 문을 사용하지 않고 최소 두 정수를 찾는 방법과 임시 변수를 사용하지 않고 두 정수를 바꾸는 방법과 같은 다양한 비트 트릭을 시연합니다. 발표자는 예측할 수 없는 분기에 대해 논의하고 예측 가능한 분기를 사용할 수 없는 경우를 위한 분기 없는 최소 비트 트릭을 소개하며 비트 해킹이 분할과 같은 비용이 많이 드는 작업을 단순한 비트 연산으로 대체하여 코드를 최적화할 수 있는 방법을 보여줍니다. 비디오는 또한 de Bruijn 시퀀스와 N Queens 문제와 같은 문제를 해결하는 데 적용하는 방법에 대해 설명합니다.
두 번째 부분에서는 비트 벡터를 사용하여 N Queens 문제를 해결하고 이진 단어에서 1비트의 수를 효율적으로 계산하는 방법에 대해 설명합니다. N Queens 문제를 구현하기 위해 역추적을 사용하고 보드를 효율적으로 표현하기 위해 비트 벡터를 사용합니다. N Queens 문제에서 여왕을 안전하게 배치하기 위한 세 가지 검사를 설명하고, 최하위 1비트를 재귀적으로 제거하여 단어의 1비트 수를 세는 방법을 제시합니다. 또한 테이블 조회 및 레지스터 조작을 사용하여 1비트 수를 계산하는 방법도 설명합니다. 비디오는 단어 길이의 로그 밑수 2에 비례하는 성능을 갖는 1비트를 계산하는 분할 정복 방식의 시연으로 끝납니다. 추가 학습을 위한 리소스도 제공됩니다.
강의 4. 어셈블리 언어와 컴퓨터 아키텍처
강의 4. 어셈블리 언어와 컴퓨터 아키텍처
이 비디오는 어셈블리 언어 및 컴퓨터 아키텍처에 대한 포괄적인 개요를 제공합니다. 어셈블리 언어는 코드 성능을 최적화하기 위한 중요한 인터페이스이며 컴퓨터 아키텍처를 이해하는 것은 어셈블리 언어를 마스터하는 데 필수적입니다. 연사는 x86 64 아키텍처의 역사와 개발, 키 레지스터, 데이터 유형, 메모리 주소 지정 모드, 명령어 세트 아키텍처(스택, 정수 및 이진 논리, 부울 논리 및 서브루틴 포함)에 대해 설명합니다. 또한 0 및 부호 확장과 같은 확장과 어셈블리 언어의 다양한 주소 지정 모드에 대해서도 설명합니다. 또한 비디오에서는 부동 소수점 유형, 벡터 및 벡터 단위, 기존 및 SSE 명령어, 수퍼스칼라 처리, 비순차 실행, 분기 예측과 같은 컴퓨터 아키텍처 설계 기능에 대해 설명합니다.
비디오는 또한 어셈블리 언어 및 컴퓨터 아키텍처와 관련된 여러 주제를 다룹니다. 중심 주제 중 하나는 데이터 종속성과 같은 위험으로 인해 발생하는 명령 수준 병렬 처리(ILP) 및 파이프라인 중단입니다. 발표자는 실제, 안티 및 출력 데이터 종속성과 수퍼 스칼라 프로세서가 하드웨어에서 더 많은 병렬성을 활용하여 한 번에 여러 명령을 실행할 수 있는 방법에 대해 논의합니다. 그러나 위험을 피하기 위해 아키텍트는 이름 변경 및 재정렬과 같은 전략과 브랜치의 결과를 추측하고 미리 실행하는 예측 실행을 구현했습니다. 연사는 청중이 소프트웨어 최적화를 더 잘 이해하기 위해 이러한 방법을 이해하도록 권장합니다.
강의 5. C에서 어셈블리로
강의 5. C에서 어셈블리로
비디오의 이 부분에서는 컴파일러를 사용하여 어셈블리 언어에서 C 코드를 구현하는 방법과 함께 어셈블리 언어에 대한 C 이해의 중요성에 대해 설명합니다. 초점은 특히 Linux x86 64 호출 규칙에서 LLVM IR이 어셈블리로 변환되는 방식에 있습니다. 발표자는 LLVM IR의 기본 구성 요소와 C 프로그래밍 언어의 구문이 LLVM IR로 변환되는 방법을 설명합니다. 비디오는 또한 가상 메모리의 레이아웃, 여러 함수 간의 함수 호출 조정 문제, Linux x86 64 호출 규칙의 두 포인터(BP 및 SP)를 사용하여 모든 스택 프레임을 관리하는 방법을 다룹니다.
이 비디오는 또한 레지스터를 호출자 저장 또는 수신자 저장으로 저장하는 것과 같이 C에서 어셈블리 프로그래밍으로 레지스터 상태를 유지하기 위한 전략과 x86 호출 규칙이 작업 낭비를 방지하는 방법을 설명합니다. C 및 어셈블리에서 함수 호출이 작동하는 방식을 다루고 인수 및 로컬 변수를 스택에 저장하는 프로세스와 기본 포인터 대신 스택 포인터를 사용하는 일반적인 최적화에 대해 설명합니다. 비디오는 또한 제어 흐름 그래프를 사용하여 LV miR을 어셈블리 코드로 컴파일하고 함수 프롤로그에 대해 논의하고 레지스터를 저장하고 조건을 처리하고 C 코드를 어셈블리 코드로 변환하는 과정을 보여줍니다. 마지막으로 결과를 반환하기 전에 레지스터를 복원하는 데 사용되는 함수 에필로그에 대해 설명합니다.
레지스터, 호출 규칙은 각 함수가 사용할 수 있는 레지스터에 대한 규칙과 함수 호출을 통해 해당 레지스터를 보존하는 방법을 자세히 설명합니다.
강의 6. 멀티코어 프로그래밍
강의 6. 멀티코어 프로그래밍
이 동영상 강의에서는 멀티코어 프로그래밍과 무어의 법칙으로 인한 멀티코어 프로세서의 등장과 클록 주파수 스케일링의 종말에 대해 설명합니다. 발표자는 프로세서가 직면한 전력 밀도 문제와 무어의 법칙을 따라가기 위해 칩에 다중 코어를 추가하게 된 방법을 설명합니다. 강의는 또한 병렬 프로그래밍을 위한 추상화를 제공하는 Pthreads, TBB, OpenMP 및 Silk와 같은 공유 메모리 하드웨어 및 동시성 플랫폼의 캐시 일관성 프로토콜의 기본 사항을 다룹니다. 피보나치 프로그램을 구현하는 예를 통해 각 플랫폼의 장단점을 논의하고 시연합니다. 이 비디오는 멀티 코어 프로그래밍에 대한 포괄적인 개요와 프로그래머가 직면한 문제 및 솔루션을 제공합니다.
비디오는 또한 병렬 처리를 처리하기 위한 추상화 도구인 Silk의 다양한 측면을 다룹니다. 발표자는 중첩된 실크 for 루프, 어셈블리 코드 생성, 리듀서를 사용한 축소, 스케줄러 및 성능 최적화와 같은 주제에 대해 논의합니다. 또한 각각 디버깅 및 확장성 분석을 위한 Silk Sanitizer 및 Silk Scale과 같은 관련 도구와 Silk 생태계에 대한 개요를 제공합니다. 요점은 멀티코어 프로세서를 위한 병렬 프로그램을 작성하는 것이 어려울 수 있지만 Silk는 복잡한 작업을 효율적으로 처리하여 프로세스를 단순화하여 프로그래머가 코드 실행을 더 잘 제어할 수 있도록 한다는 것입니다.
강의 7. 인종과 병렬성
강의 7. 인종과 병렬성
이 비디오는 Silk 프로그래밍의 경합, 병렬 처리 및 계산 dag와 관련된 다양한 주제를 다룹니다. 다루는 몇 가지 주요 개념에는 동시 실행을 위한 spawn 및 sync 문, 경합 조건 방지의 중요성 및 이를 식별하기 위한 Silk의 경합 감지기 사용이 포함됩니다. 이 비디오는 또한 작업 및 계산 범위를 분석하는 방법과 함께 프로그램에서 병렬 처리의 양을 정량화하는 방법으로 Amdahl의 법칙, 작업 법칙 및 범위 법칙을 다룹니다. 병렬 정렬 알고리즘의 잠재적인 속도 향상 및 병렬 처리와 스케줄링 이론의 개념도 탐욕스러운 스케줄러의 정리에 중점을 두고 논의됩니다. 전반적으로 비디오는 Silk 프로그래밍에서 프로그램 성능을 이해하고 최적화하는 데 유용한 통찰력을 제공합니다.
이 비디오는 T1/Tinfinity가 P^2보다 크거나 같은 한 모든 욕심쟁이 스케줄러가 거의 완벽한 선형 속도 향상을 달성한다고 기본적으로 명시하는 욕심쟁이 스케줄러 경계의 결과를 설명합니다. 작업 도용 스케줄러를 사용하는 실크 스케줄러는 프로세서 수가 T1/Tinfinity보다 훨씬 적은 한 거의 완벽에 가까운 선형 속도 향상을 달성할 수 있습니다. 실크 런타임 시스템은 준비된 가닥의 작업 데크를 유지 관리하여 작동하고 스택처럼 데크의 바닥을 조작합니다. 이 비디오는 또한 여러 스택 보기를 병렬로 허용하고 병렬 함수 호출을 가능하게 하는 Cactus Stack에 대해 설명합니다. P 프로세서 실행에 필요한 스택 공간의 상한선은 각 프로세서가 작업을 도용할 때마다 계산 그래프 아래로 완전히 내려갈 필요가 없기 때문에 필요한 실제 양보다 훨씬 느슨한 경우가 많습니다.
강의 8. 멀티스레드 알고리즘 분석
강의 8. 멀티스레드 알고리즘 분석
이 비디오는 나누기 및 정복 반복을 분석하기 위한 마스터 방법에 대해 설명하고 n의 증가와 필요한 작업을 결정하기 위해 n의 로그 밑 B와 A의 로그 밑 B를 N의 F와 비교하여 멀티스레드 알고리즘에 적용합니다. 이 비디오는 기본 멀티스레드 알고리즘에 대한 솔루션이 포함된 치트 시트를 제시하고 작업 및 범위 분석, 작업 효율성, 입자 크기 최적화를 통한 오버헤드 비용 극복과 같은 주제를 다룹니다. 기술적인 주제를 전달할 때 공감의 중요성이 강조되고, 병렬 처리를 높이고 실행 시간을 줄이기 위해 작업과 범위의 균형을 맞추는 수단으로 DAG 개념이 도입됩니다.
이 비디오는 작업 및 스팬에 초점을 맞춘 멀티스레드 알고리즘 분석과 스팬을 최소화하면서 병렬 처리를 최대화하여 거의 완벽한 선형 속도 향상을 달성하는 방법에 대해서도 설명합니다. 발표자는 스레드에 할당된 작업 수가 충분히 많은 다중 스레드 알고리즘에 대한 분할 및 정복 접근 방식을 제안하고 스케줄링 오버헤드로 인해 수많은 작은 작업을 생성하지 않도록 경고합니다. 제시된 예제 코드에는 효율적인 코드와 형편없는 코드가 포함되어 있습니다. 연사는 또한 2차원 코딩 및 인덱싱에서 부분 행렬을 표현하는 방법에 대해 논의하고 분할 및 정복 행렬 곱셈 코드에서 '제한'을 사용하여 성능을 향상시키는 방법을 강조합니다.
강의 9. 컴파일러가 할 수 있는 것과 할 수 없는 것
강의 9. 컴파일러가 할 수 있는 것과 할 수 없는 것
이 비디오는 다양한 예제를 사용하여 컴파일러가 코드를 최적화하는 방법에 대해 설명합니다. 컴파일러가 불필요한 스토리지 및 메모리 참조를 제거하는 방법과 루프를 최적화하여 성능을 향상시키는 방법에 대해 설명합니다.
이 비디오는 또한 컴파일러 최적화 단계의 개념과 이를 사용하여 코드 성능을 개선하는 방법에 대해서도 설명합니다. 또한 특히 벡터화와 관련하여 컴파일러의 제한 사항에 대해서도 설명합니다. 컴파일러는 코드의 포인터가 앨리어스되지 않는다는 것을 확인할 수 있는 경우에만 코드를 벡터화할 수 있습니다. 포인터가 별칭을 지정하면 컴파일러는 코드를 벡터화할 수 없습니다. 프로그래머는 포인터 사용에 대한 자세한 정보를 제공하도록 포인터에 주석을 달아 컴파일러를 도울 수 있습니다.