이 비디오에서 연사는 정확도에 영향을 미칠 수 있는 외부 요인을 포함하여 컴퓨팅에서 측정 및 타이밍의 다양한 측면에 대해 논의합니다. 그들은 모델의 필요성과 데이터에 대한 명확한 이해, 오류를 보상하기 위한 분산 감소, 신뢰성을 보장하기 위한 적절한 타이밍 호출 사용을 강조합니다. 또한 성능 모델링, 타이밍 호출, 하드웨어 카운터 및 시뮬레이터와 같은 도구를 강조하면서 전력 법칙 및 비결정론적 요인과 같은 소프트웨어 성능을 정확하게 측정하는 데 따르는 문제에 대해 논의합니다. 마지막으로 그들은 정확한 결과를 보장하기 위한 기술로 삼각 측량 및 적응을 권장하면서 단일 도구에 의존하지 않도록 주의합니다.
연사는 성능 소프트웨어 엔지니어링에서 신뢰할 수 있는 성능 측정의 중요성을 설명합니다. 그는 통계를 사용하여 성능을 정확하게 측정할 것을 권장하고 다양한 상황에서 유용한 성능 측정을 제공할 수 있는 평균과 같은 다양한 유형의 요약 통계에 대해 설명합니다. 그는 비율의 산술 평균을 취하는 것이 유효한 접근 방식이 아니라고 지적하고 대신 기하 평균을 사용할 것을 제안합니다. 연사는 프로그램을 비교할 때 데이터를 집계하는 올바른 방법을 선택하는 것의 중요성을 강조하고 성능을 보다 정확하게 비교하기 위해 여러 실행에서 최소 또는 10%와 같은 낮은 차수 통계를 취할 것을 제안합니다. 연사는 또한 일대일 비교 및 통계 도출을 위한 모델 피팅을 포함하여 성능을 측정하고 비교하는 다양한 방법론에 대해 논의하지만 모델링의 과적합 문제에 대해 경고합니다. 전반적으로 비디오는 프로그램 성능 향상을 위한 신뢰할 수 있는 성능 측정의 중요성을 강조합니다.
00:00:00 이 섹션에서 화자는 이전 학생 중 한 명이 수행한 정렬 코드에 대한 연구에 대해 논의합니다. 이 코드는 time.h 헤더 파일을 사용하여 타이밍 측정을 위한 clock get time 루틴에 액세스합니다. 분류 루틴은 시간이 지정되고 경과 시간이 계산되어 출력됩니다. 측정된 실행 시간의 그래프는 정렬 루틴이 대부분 N log N 성장을 따르지만 측정된 시간은 가장 큰 어레이의 경우에도 느리다는 것을 보여줍니다.
00:05:00 이 섹션에서 교수는 관찰 중인 데이터에 대한 모델을 갖는 것의 중요성에 대해 논의합니다. 그는 측정된 데이터가 예상한 것과 크게 다른 예를 제시하고 학생들에게 이 편차에 대한 가능한 가설을 제안하도록 요청합니다. 어떤 사람들은 그것이 캐시나 타이밍의 정밀도에 문제가 있을 수 있다고 생각했지만, 교수는 편차를 일으키는 기계에서 실행 중인 관련 없는 프로세스가 있을 수 있다고 지적합니다. 이 경우 문제는 머신이 둘 이상의 프로세스에서 동시에 사용되는 다중 테넌시에 있습니다. 교수는 품질 측정의 필요성과 데이터의 의미에 대한 명확한 이해를 강조합니다.
00:10:00 이 섹션에서는 스피커가 컴퓨팅의 측정 및 타이밍에 대해 논의하고 외부 요인이 측정 정확도에 어떤 영향을 미칠 수 있는지에 대해 설명합니다. 그들은 특히 측정 결과에 상당한 영향을 미칠 수 있는 시스템 온도 및 절전 기술로 인해 클록 주파수 변경이 어떻게 발생할 수 있는지에 중점을 둡니다. 스피커는 클록 주파수와 전압을 트랜지스터에 조정하여 전력을 줄이는 기술인 동적 주파수 및 전압 스케일링의 개념을 소개합니다. 그들은 부정확한 결과를 피하기 위해 측정을 할 때 외부 요인을 고려하는 것이 중요하다고 강조합니다.
00:15:00 이 섹션에서 발표자는 전기 엔지니어가 사용하는 전력 법칙으로 인해 소프트웨어 성능을 측정하는 문제에 대해 논의합니다. 멱법칙에 따르면 전력은 CV 제곱 F와 같습니다. 여기서 C는 동적 정전 용량, V는 공급 전압, F는 클록 주파수입니다. 전력과 열을 줄이기 위해 주파수와 전압을 낮추면 전력이 세제곱씩 감소합니다. 이는 소프트웨어 성능을 안정적으로 측정하는 데 어려움이 있으며 스피커는 정확한 측정을 위해 일부 노이즈를 제거하여 정지 시스템을 제안합니다. 또한 성능 모델링과 같은 소프트웨어 성능 측정 도구에 대해서도 설명합니다.
00:20:00 이 섹션에서 발표자는 특히 성능 엔지니어링의 맥락에서 측정 및 타이밍과 관련하여 분산을 줄이는 것의 중요성에 대해 논의합니다. 가변성을 줄임으로써 체계적이고 무작위적인 측정 오류를 보상하고 프로그램을 비교하기 위해 더 적은 시행을 요구할 수 있습니다. 연사는 또한 백그라운드 작업, 인터럽트, 스레드 배치 등을 포함하여 컴퓨터 시스템의 다양한 가변성 원인을 지적합니다. 마지막으로 그는 분산이 높은 상태에서 측정하면 신뢰할 수 없는 결과가 나올 수 있으므로 시스템을 변경하기 전에 먼저 분산을 줄이는 데 초점을 맞추는 것이 중요하다고 강조합니다.
00:25:00 이 섹션에서 발표자는 프로세서의 하이퍼 스레딩 개념과 이것이 클라우드 시스템에서 부정확한 측정으로 이어질 수 있는 방법에 대해 이야기합니다. 하이퍼 스레딩은 하나의 기능 장치를 통해 두 개의 명령 스트림을 실행하여 두 개의 프로세서처럼 보이지만 실제로는 두 개의 별도 프로세서가 아닌 20%의 속도 향상만 제공합니다. 발표자는 또한 측정 결과에 상당한 영향을 미칠 수 있는 터보 부스트 및 시스템 정지와 같은 다른 기술에 대해서도 논의합니다. 하이퍼 스레딩과 터보 부스트를 끄고 모든 악마를 정지시킴으로써 발표자와 그의 그룹은 최소 실행 시간보다 1% 미만 느린 매우 안정적인 측정을 달성할 수 있었습니다.
00:30:00 이 섹션에서 발표자는 최신 하드웨어에서 실행되는 프로그램의 결정성에 영향을 줄 수 있는 다양한 요소에 대해 이야기합니다. 프로그램을 보다 결정론적으로 만들기 위해 취할 수 있는 특정 조치가 있지만 비결정론적 요소를 완전히 제거하는 것은 불가능합니다. 캐싱, 인터럽트, 스레딩 및 분기 예측과 같이 프로그램 실행 중에 발생할 수 있는 대부분의 비결정적 요소는 결정적 프로세스입니다. 그러나 하드웨어의 임의성은 사용자가 제어할 수 없으며 메모리 오류가 발생할 수 있습니다. 발표자는 코드 정렬이 프로그램 결정론에 차이를 만들 수 있으며 코드에 변경 사항이 있으면 캐시 정렬이 변경되어 프로그램 결정론에 영향을 미칠 수 있다고 제안합니다.
00:35:00 이 섹션에서 연사는 작은 변화가 프로그램 성능에 얼마나 큰 영향을 미칠 수 있는지에 대해 논의합니다. 예를 들어 1바이트를 삽입하면 이후의 모든 항목이 선형적으로 영향을 받을 수 있으며 링커 명령줄에 dot o 파일이 나타나는 순서를 변경하면 -OH-와 -O3 사이를 이동하는 것보다 더 큰 영향을 미칠 수 있습니다. 이러한 문제를 해결하기 위해 컴파일러는 문제를 인식하고 더 많은 정렬을 수행하고 있습니다. LLVM에는 함수의 모든 함수와 블록을 정렬할 수 있는 스위치가 있지만 정렬로 인해 프로그램 속도가 느려질 수 있습니다. 또한 프로그램 이름은 실행 파일 이름이 호출 스택에서 끝나는 환경 변수로 끝나므로 속도에 영향을 줄 수 있습니다.
00:40:00 이 섹션에서 발표자는 time 명령을 사용하여 외부에서 프로그램 측정, clock get time 또는 기타 방법을 사용하여 프로그램에 타이밍 호출 넣기, gdb로 프로그램 중단 등 소프트웨어 성능을 측정하기 위한 다양한 도구와 방법에 대해 논의합니다. 시간이 가장 많이 걸리는 루틴을 식별하기 위해 perf 도구 세트에 사용되는 것과 같은 하드웨어 및 OS 지원을 활용하거나 프로그램을 시뮬레이션하여 더 깊이 이해하지만 속도는 더 느립니다. 발표자는 time 명령을 사용할 때 경과 시간, 사용자 시간 및 시스템 시간 간의 차이와 프로세서 할당으로 인해 총 시간에 합산되지 않을 수 있는 방법에 대해 설명합니다.
00:45:00 이 섹션에서 발표자는 벽시계 시간, 사용자 모드에서 소비된 프로세서 시간 및 커널에서 소비된 시간을 포함하여 다양한 유형의 타이밍 및 측정에 대해 논의합니다. 사용에 권장되는 타이밍 호출은 절대 뒤로 실행하지 않도록 보장하는 클록 단조 옵션이 있는 클록 가져오기 시간입니다. 실행하는 데 비결정적 시간이 걸릴 수 있지만 다른 코어에서 다른 답변을 제공하고 역방향으로 실행될 수 있는 RTIDTSC와 같은 다른 타이머보다 더 안정적입니다. 화자는 get time of day를 사용하지 말라고 경고합니다.
00:50:00 이 섹션에서 연사는 clock_gettime 사용 및 time 명령으로 측정을 포함하여 프로그래밍에서 이벤트를 측정하고 시간을 재는 다양한 방법에 대해 설명합니다. 그들은 시간이 지남에 따라 기술이 변경될 수 있고 엔지니어가 적응해야 할 수도 있다고 경고합니다. 또한 화자는 간단한 프로파일링 기법으로 임의의 순간에 코드를 인터럽트하는 것을 제안하며 Facebook과 같은 대기업이 이 방법을 사용한다고 언급합니다. 또한 발표자는 프로세스별로 이러한 카운터에 액세스할 수 있는 하드웨어 카운터 및 라이브러리 livepFM4에 대한 아이디어를 소개합니다. 그들은 엔지니어가 외과적으로 정밀한 도구가 항상 필요한 것은 아니며 때때로 간단한 도구로도 작업에 충분할 수 있음을 강조합니다.
00:55:00 이 섹션에서 발표자는 하드웨어 카운터 및 시뮬레이터를 포함하여 측정값을 수집하는 다양한 방법에 대해 설명합니다. 그들은 많은 하드웨어 카운터가 제대로 문서화되지 않았으며 일부 도구는 4개 또는 5개 이상의 카운터가 사용되는 경우 대역폭을 시분할한다고 경고합니다. 시뮬레이터는 반복성으로 칭찬을 받지만 캐시의 모든 것을 모델링할 수는 없습니다. 화자는 정확도를 보장하기 위해 삼각 측량과 최소 두 가지 측정을 사용할 것을 권장합니다. 그들은 또한 데이터 해석을 안내하는 성능 모델의 중요성을 강조합니다.
01:00:00 이 섹션에서 발표자는 프로그램을 가져와서 변경하고 성능을 측정하여 더 빠른 프로그램을 생성하는 것과 관련된 성능 소프트웨어 엔지니어링 프로세스를 설명합니다. 그러나 신뢰할 수 있는 성능 측정은 결과를 합산하고 정확하게 도출하는 작은 변화를 만드는 데 필수적입니다. 따라서 연사는 무슨 일이 일어나고 있는지에 대한 정확한 그림을 얻기 위해 통계를 사용할 것을 권장합니다. 그는 또한 결정론적 프로그램의 원시 성능을 측정하는 것과 관련된 퍼즐을 제공하고 최소값을 사용하는 것이 노이즈를 제거하고 프로그램의 기본 하드웨어 성능을 결정하는 가장 좋은 방법이라고 결론을 내립니다.
01:05:00 이 섹션에서는 다양한 상황에서 유용한 성능 측정을 제공할 수 있는 평균을 포함하여 다양한 유형의 요약 통계에 대해 설명합니다. 웹 서버를 평가할 때 CPU 사용률과 총 작업 완료 시간은 산술 평균을 사용하여 측정할 수 있으며 벽시계 시간과 백분위수 동작은 요청 만족을 최적화하는 데 더 관련이 있을 수 있습니다. 그러나 프로그램 A와 B의 성능을 비교하는 것과 같이 비율을 요약할 때 산술 평균을 취하는 것은 일반적으로 잘못 사용되지만 유효한 접근 방식이 아닙니다. 이것은 비율의 평균이 비디오에 제공된 예에서 설명한 비율 자체와 동일하지 않기 때문입니다.
01:10:00 이 섹션에서 발표자는 성능 측정 시 비율과 수단을 비교하는 문제에 대해 논의합니다. 그들은 비율의 산술 평균을 취하는 것이 의심스러운 결과를 초래할 수 있으며 기하 평균을 사용하는 것이 더 낫다는 것을 보여줍니다. 또한 비율을 비교할 때 조화 평균이 종종 유용하다는 점에 주목합니다. 프로그램을 비교할 때 데이터를 집계하는 올바른 방법을 선택하는 것의 중요성을 강조하고 발표자는 성능을 보다 정확하게 비교하기 위해 다중 실행에서 최소 또는 10%와 같은 낮은 차수 통계를 취할 것을 제안합니다.
01:15:00 이 섹션에서 발표자는 성능 측정 및 비교를 위한 다양한 방법론에 대해 논의합니다. 한 가지 접근 방식은 10% 가장 저렴한 옵션을 비교하고 노이즈 감소를 수행하여 평균을 비교하는 것입니다. 단, 결정적인 증거를 제공하지는 않습니다. 또는 A와 B 사이에서 일대일 비교를 수행하여 어느 쪽이 더 자주 이기는지 확인할 수 있습니다. 이를 통해 귀무가설을 검증할 수 있고, 편차가 유의한지 여부를 판단하기 위한 p-value를 구할 수 있다. 이 방법은 사회 과학에서 일반적으로 사용되며 시끄러운 환경에서 유용할 수 있습니다. 마지막으로 연사는 통계를 도출하기 위해 모델을 맞추는 아이디어에 대해 간략하게 언급하고 최소 제곱 근사법의 사용에 대해 논의합니다.
01:20:00 이 섹션에서 발표자는 모델링의 과적합 문제와 어떻게 더 많은 기본 함수를 추가하면 데이터 적합성을 개선할 수 있지만 과적합으로 이어질 수 있는지에 대해 논의합니다. 해결책은 기본 기능을 제거하고 모델의 품질에 영향을 미치는지 확인하는 것입니다. 연사는 또한 측정의 구루로 알려진 Lord Kelvin을 언급하는데, 그는 측정하는 것은 아는 것이며 측정할 수 없으면 개선할 수 없다고 말했습니다. 비디오는 화자가 화요일 퀴즈에서 행운을 빌어주는 것으로 마무리됩니다.
강사는 이 비디오에서 메모리 할당과 해제를 모두 다루는 스토리지 할당에 대해 설명합니다. 고정 및 가변 크기 할당 체계뿐만 아니라 스택 및 힙을 포함하여 다양한 유형의 스토리지가 처리됩니다. 사용 가능한 목록 또는 디스크 페이지당 비트맵과 같은 솔루션을 사용하여 분산되는 메모리 블록으로 인해 발생하는 외부 조각화에 대해서도 설명합니다. 참조 카운팅 및 이 알고리즘의 한계를 포함하여 가비지 수집의 개념도 소개됩니다. "표시 및 스윕" 및 "정지 및 복사" 가비지 수집 절차도 설명되며, 후자가 조각화를 해결하는 방법과 포인터 업데이트로 인해 발생할 수 있는 정확성 문제에 중점을 둡니다. 비디오는 중지 및 복사 알고리즘의 시간 및 공간 복잡성과 외부 조각화 제거에 대한 메모로 끝납니다.
이 비디오는 Buddy 시스템, 표시 및 스윕 절차, 최적화, 세대별 및 실시간 가비지 수집, 다중 스레드 저장소 할당 및 병렬 가비지 수집을 포함하여 동적 저장소 할당과 관련된 다양한 주제를 다룹니다. 강사는 세대별 가비지 컬렉션이 프로그램 실행 중에 백그라운드에서 실시간 가비지 컬렉션이 실행되는 동안 더 어린 객체가 더 자주 스캔된다는 아이디어를 기반으로 하지만 객체 및 포인터 그래프가 계속 변경되면 정확성 문제가 발생할 수 있다고 설명합니다. 마지막으로 이 강의에서는 스택 및 힙을 포함한 다양한 유형의 스토리지 할당과 참조 카운팅, 표시 및 스윕, 중지 및 복사와 같은 다양한 가비지 수집 방법을 요약합니다. 강사는 학생들이 다가오는 숙제에서 이러한 방법 중 일부를 시도하게 될 것이라고 언급합니다.
00:00:00 이 섹션에서 강사는 메모리 할당과 해제를 모두 포함하는 스토리지 할당에 대해 설명합니다. 가장 간단한 저장 형태는 스택으로, 스택 포인터를 증가시켜 메모리를 할당하고 스택 포인터를 감소시켜 해제합니다. 그러나 스택은 마지막으로 할당된 것만 해제할 수 있고 사용된 영역 중간에 있는 것은 해제할 수 없기 때문에 적용 가능성이 제한적입니다. 또한 강사는 효율성상의 이유로 스택 오버플로는 일반적으로 컴파일러에서 확인하지 않는다고 지적합니다.
00:05:00 이 섹션에서 강사는 스택과 힙의 두 가지 스토리지 유형에 대해 설명합니다. 스택은 효율적이지만 모든 용도로 사용할 수 없는 고정 크기 저장소인 반면, 힙은 더 일반적이지만 효율적으로 구성하고 사용하기 어렵습니다. 힙 할당의 경우 malloc 및 free C 함수를 사용할 수 있지만 C 및 C++에서는 가비지 수집기를 제공하지 않기 때문에 프로그래머가 메모리를 직접 관리해야 하므로 메모리 누수, 댕글링 포인터 및 이중 해제가 발생할 수 있습니다. 강사는 프로그램의 메모리 버그 수를 줄이기 위해 address sanitizer 및 Valgrind와 같은 메모리 검사기를 사용할 것을 제안합니다.
00:10:00 이 섹션에서 발표자는 고정 크기 할당부터 시작하여 스토리지를 할당하는 다양한 방법에 대해 논의합니다. 각 스토리지 조각의 크기는 동일하고 일부 블록은 사용되고 다른 블록은 사용되지 않습니다. 사용되지 않은 블록은 사용 가능한 목록이라는 목록에 보관되며 사용 가능한 목록의 각 블록에는 목록의 다음 블록에 대한 포인터가 있습니다. 자유 목록에서 하나의 객체를 할당하기 위해 프로그램은 포인터를 자유로 설정한 다음 자유 포인터가 자유 목록의 다음 항목을 가리키도록 설정하고 포인터를 자유 목록의 첫 번째 객체로 반환합니다. 할당을 해제하려면 객체의 다음 포인터를 해제하고 해제할 객체와 동일하게 해제하면 됩니다. 무료 목록을 사용하면 할당 및 해제에 일정한 시간이 걸리며 시간적 지역성도 좋습니다.
00:15:00 이 섹션에서는 사용된 메모리 블록이 모든 메모리 공간에 분산될 때 발생하는 외부 조각화의 개념을 소개합니다. 이로 인해 페이지 테이블이 커져 디스크 스래싱(thrashing)이 발생하고 번역 검색 효율이 떨어질 수 있습니다. 외부 조각화를 완화하기 위해 디스크 페이지당 사용 가능한 목록 또는 비트맵을 사용할 수 있으며 전체 페이지에서 할당하고 스토리 블록을 해제하고 빈 페이지를 페이징 아웃할 수 있습니다. 고정 크기 힙 할당은 외부 조각화를 줄이는 데에도 유용할 수 있습니다. 마지막으로 다양한 크기의 할당된 메모리에 대해 사용 가능 목록의 효율성을 활용하는 빈 사용 가능 목록과 함께 가변 크기 힙 할당을 사용할 수 있습니다.
00:20:00 이 섹션에서는 메모리 할당 시스템에서 다양한 크기의 메모리 블록을 저장하는 방식을 제시합니다. 이 방식은 블록을 크기에 따라 빈으로 나누고 각 빈은 2의 거듭제곱인 지정된 크기의 블록을 보유합니다. 메모리를 할당할 때 요청된 크기에 따라 적절한 빈이 선택되고 비어 있는 경우 비어 있지 않은 더 큰 빈을 더 작은 청크로 분할하여 원하는 크기를 얻습니다. 그러나 이 방식은 메모리의 내부 단편화를 초래할 수 있어 낭비가 심하므로 사용되는 빈의 수가 제한되고 작은 블록을 페이지로 그룹화하여 오버헤드를 줄입니다. 필요한 경우 운영 체제를 사용하여 더 많은 메모리를 제공할 수 있으며 이러한 목적으로 사용할 수 있는 시스템 호출이 있습니다.
00:25:00 이 섹션에서 비디오는 메모리 할당이 어떻게 작동하는지 설명하고 'malloc'의 표준 구현이 운영 체제에서 메모리를 가져오기 위해 'break'와 같은 명령에 의존한다는 점에 주목합니다. OS는 많은 양의 메모리를 제공하며 이를 더 작은 블록으로 나누는 것은 스토리지 할당 시스템에 달려 있습니다. 이 섹션에서는 블록 크기를 저장하는 다양한 방식과 가상 메모리 주소 공간이 프로그램에 배치되는 방식을 포함하여 메모리 할당자의 변형에 대해서도 다룹니다. 스택과 힙이 서로를 향해 성장하지만 절대 교차하지 않는다는 점에 주목합니다. 마지막으로 프로그램에서 큰 상수 테이블을 미리 계산하면 데이터 세그먼트에서 읽어야 하므로 로딩 시간이 늘어날 수 있습니다.
00:30:00 이 섹션에서는 외부 조각화, 페이지 테이블의 성능 저하, 디스크 스래싱 및 메모리가 분산된 경우 낮은 TLB 적중률로 이어질 수 있는 가상 메모리의 조각화 문제에 대해 설명합니다. 스토리지 할당의 목표는 사용된 메모리 부분을 압축하면서 가능한 한 적은 가상 메모리를 사용하는 것입니다. 빈 사용 가능 목록 할당 체계는 힙 저장소에서 소비하는 가상 메모리의 양이 M log M의 상한이라는 정리와 함께 분석됩니다. 더 작은 블록을 더 큰 블록으로 병합하면 빈 사용 가능 목록 체계를 개선할 수 있지만 오버헤드는 이 방법은 Charles Leiserson의 논문에 따르면 최적 할당자보다 더 나쁜 상수 요소인 표준 빈 사용 가능 목록 알고리즘에 비해 높을 수 있습니다.
00:35:00 이 섹션에서 발표자는 스토리지 할당의 개념과 힙 스토리지를 처리할 때 조각화를 줄이는 방법을 설명합니다. 그는 또한 프로그래머가 개체를 수동으로 해제할 필요가 없도록 하는 가비지 수집에 대한 아이디어에 대해서도 설명합니다. 연사는 세 가지 유형의 메모리 개체(루트, 라이브 개체 및 죽은 개체)와 가비지 수집이 후자를 재활용할 수 있는 방법을 설명합니다. 마지막으로 객체를 참조하는 포인터의 수를 세어 객체가 해제될 수 있는지 판단하는 단순한 형태의 가비지 수집인 참조 횟수에 대해 설명합니다.
00:40:00 이 섹션에서 연사는 가비지 수집 방식으로 참조 카운팅의 개념을 소개하고 참조 카운트 알고리즘이 어떻게 작동하는지 설명합니다. 그러나 참조 그래프의 주기를 수집할 수 없는 알고리즘의 한계가 지적됩니다. 그런 다음 발표자는 이러한 제한을 피하기 위해 일부 프로그래밍 언어에서 강력한 포인터와 약한 포인터를 사용하는 방법에 대해 논의합니다. 마지막으로 발표자는 참조 그래프에서 주기를 처리할 때 참조 카운팅의 제한을 피하는 두 가지 다른 가비지 수집 방식인 "표시 및 스윕"과 "정지 및 복사"를 미리 봅니다.
00:45:00 이 섹션에서 발표자는 너비 우선 검색 알고리즘을 사용하여 메모리에서 모든 라이브 개체를 찾는 방법에 대해 설명합니다. 2개의 포인터가 있는 배열은 검색을 위한 FIFO 대기열을 나타내는 데 사용되며 알고리즘은 루트에서 도달할 수 있는 각 라이브 개체를 표시합니다. 검색이 완료되면 표시되지 않은 개체를 가비지 수집에 사용할 수 있습니다. Mark-and-Sweep 절차에는 두 단계가 포함됩니다. 즉, 너비 우선 검색 알고리즘을 포함하는 Marked 단계와 표시되지 않은 개체를 해제하기 위해 메모리를 스캔하는 Sweep 단계입니다. 그러나 이 체계에는 모든 메모리를 스캔해야 하고 참조되지 않은 개체를 보는 것과 관련된 오버헤드와 같은 제한이 있습니다.
00:50:00 이 섹션에서는 조각화를 처리하는 "중지 및 복사" 가비지 수집 절차를 소개합니다. 이 절차는 표시 및 스윕 알고리즘과 유사하지만 라이브 개체가 메모리에서 연속되도록 하기 위해 다른 접근 방식을 사용합니다. 프로시저는 두 개의 개별 메모리 공간(from 공간과 to 공간)을 사용하고 from 공간이 가득 찰 때까지 개체를 할당하고 해제합니다. 그런 다음 가비지 수집 알고리즘이 실행되고 두 공간은 두 공간의 메모리에 연속적으로 배치될 라이브 객체를 식별하기 위한 너비 우선 검색의 대기열로 사용됩니다. 그러나 이 알고리즘을 사용하면 from 공간의 개체를 가리키는 포인터가 더 이상 정확하지 않을 수 있는 정확성 문제가 발생할 수 있습니다. 이를 해결하기 위해 프로시저는 from 공간의 해당 개체에 전달 포인터를 저장하고 너비 우선 검색에서 개체를 큐에서 제거할 때 이러한 전달 포인터를 따라 모든 포인터를 업데이트합니다.
00:55:00 이 섹션에서 발표자는 중지 및 복사 가비지 수집 알고리즘, 시간 복잡성 및 외부 조각화를 처리하는 방법에 대해 설명합니다. 중지 및 복사 알고리즘에는 from 공간에서 to 공간으로 개체를 복사한 다음 to 공간에서 이러한 개체의 포인터를 업데이트하는 작업이 포함됩니다. 이 알고리즘은 시간과 공간에서 선형이므로 보다 효율적이고 효과적인 가비지 수집 방법입니다. from 공간이 가득 차면 사용자는 새로운 힙 공간을 요청하고 from 공간의 크기를 두 배로 늘릴 수 있습니다. 이 체계에 필요한 가상 메모리 공간은 최적의 상수배이며 이 알고리즘은 외부 조각화를 제거합니다.
01:00:00 이 섹션에서 발표자는 병합을 수행하기 위한 Buddy 시스템, 마크 및 스윕 절차의 변형, 성능 향상을 위한 최적화, 세대별 가비지 수집, 실시간 가비지 수집과 같은 동적 스토리지 할당과 관련된 더 많은 주제에 대해 논의합니다. , 다중 스레드 스토리지 할당 및 병렬 가비지 수집. 세대별 가비지 수집은 많은 객체가 수명이 짧다는 생각을 기반으로 합니다. 따라서 대부분의 시간 동안 더 어린 객체만 스캔됩니다. 실시간 가비지 수집은 프로그램이 실행되는 동안 백그라운드에서 작동하지만 개체 및 포인터의 그래프가 변경되면 정확성 문제가 발생할 수 있습니다. 다중 스레드 스토리지 할당 및 병렬 가비지 수집에는 여러 스레드가 실행되므로 경합 및 기타 정확성 문제를 처리하는 알고리즘이 더 까다로워집니다. 연사는 또한 스택 및 힙을 포함한 다양한 유형의 스토리지 할당과 참조 카운팅, 표시 및 스윕, 중지 및 복사와 같은 가비지 수집을 수행하는 다양한 방법을 요약합니다.
01:05:00 이 섹션에서 강사는 스토리지 할당 체계에 대해 자세히 알아볼 것이며 학생들이 다가오는 숙제에서 그 중 일부를 시도해 볼 기회를 갖게 될 것이라고 언급했습니다. 그런 다음 강사는 강의를 종료하고 추가 질문을 위해 바닥을 열었습니다.
이 비디오에서는 다양한 메모리 할당 전략과 장단점에 대해 설명합니다. malloc 및 정렬된 할당의 사용과 free로 적절한 메모리 할당 해제의 중요성이 설명됩니다. 외부 조각화 및 느린 성능 문제와 함께 가상 메모리 할당을 위한 Mmap 사용도 다룹니다. 스택 프레임을 할당하기 위한 힙 기반 선인장 스택 접근 방식을 강조하여 C 및 C++ 프로그래밍의 스택 개념을 살펴보고 더 나은 공간 제한 증명 및 상한으로 이어질 수 있습니다. 조각화를 최소화하기 위해 작은 블록을 최적화하는 것의 중요성과 함께 선형 스택 풀의 사용에 대해서도 설명합니다. 이 비디오는 이러한 문제를 해결하기 위한 빈 사용 가능 목록 및 주기적인 메모리 재조정과 같은 접근 방식과 함께 글로벌 및 로컬 힙 접근 방식과 잠재적인 문제에 대한 논의로 끝납니다.
비디오는 또한 병렬 스토리지 할당을 위한 솔루션에 대해 설명하고 Hoard 할당자를 솔루션으로 소개합니다. Hoard 할당자는 잘못된 공유를 줄이고 확장성을 개선하며 외부 조각화를 줄이기 위해 힙 간에 이동할 수 있는 대형 수퍼 블록과 로컬 및 글로벌 힙의 조합을 사용합니다. 글로벌 힙에 할당된 최대 스토리지는 로컬 힙에 할당된 최대 스토리지이며, 풋프린트는 사용자 풋프린트와 로컬 힙에서 할당되었지만 사용되지 않은 스토리지의 상한입니다. 비디오는 또한 Je malloc 및 Super malloc과 같은 다른 할당자에 대해 간략하게 설명하며 벤치마크 결과는 Super malloc이 Je malloc 및 Hoard보다 성능이 더 우수함을 나타냅니다. 토론은 가비지 수집 세부 정보에 대한 온라인 슬라이드를 참조하는 것으로 끝납니다.
00:00:00 이 섹션에서 강사는 malloc 및 정렬된 할당을 포함하여 메모리 할당 프리미티브를 검토합니다. 정렬된 할당은 메모리를 캐시 라인에 정렬하는 데 사용할 수 있으므로 캐시 라인 내의 개체에 액세스하는 데 하나의 캐시 액세스만 필요하므로 캐시 미스 수를 줄일 수 있습니다. 강사는 또한 free 기능을 사용하여 메모리 할당을 적절하게 해제하고 메모리 누수 및 이중 해제를 방지하는 것의 중요성에 대해 설명합니다. 마지막으로 강사는 백업 파일 없이 가상 메모리를 할당하는 데 사용할 수 있는 시스템 호출 Mmap을 소개합니다.
00:05:00 이 섹션에서 발표자는 M 맵을 사용하여 메모리를 할당하는 프로세스를 설명합니다. 이는 요청된 메모리 크기를 보유할 수 있을 만큼 충분히 큰 응용 프로그램의 주소 공간에서 연속적으로 사용되지 않는 영역을 찾아 업데이트하는 시스템 호출입니다. 할당된 페이지에 대한 항목을 포함하는 페이지 테이블입니다. 라이브러리 호출이자 C 라이브러리의 힙 관리 코드의 일부인 malloc과 달리 M 맵은 요청된 메모리에 대한 물리적 메모리를 즉시 할당하지 않지만 수정되고 수정되는 특수한 0 페이지를 가리키는 항목으로 페이지 테이블을 채웁니다. 사용자가 처음 쓸 때만 실제 메모리로 변환됩니다. 또한 M map은 운영 체제에서 메모리를 가져오는 역할을 하며, malloc은 이전에 할당된 메모리를 재사용하여 조각화를 줄이고 시간적 지역성을 개선하는 역할을 합니다.
00:10:00 이 섹션에서는 비디오에서 스토리지 할당에 MMAP와 MALLOC를 사용하는 것의 차이점에 대해 설명하고 MMAP이 상대적으로 무겁고 작은 할당에도 전체 페이지를 할당하여 외부 조각화 및 성능 저하를 초래한다는 점을 강조합니다. 비디오는 또한 가상 주소가 메모리에 액세스하는 데 사용되고 하드웨어가 페이지 테이블에서 적절한 물리적 주소를 찾는 주소 변환 프로세스를 검토합니다. 이 비디오는 최근 페이지 테이블 조회를 캐싱하여 TLB가 작동하는 방식을 설명하고 공간적 또는 시간적 지역성을 가진 프로그램이 TLB에 저장된 많은 최근 액세스를 가지므로 성능이 더 빨라진다는 점에 주목합니다.
00:15:00 이 섹션에서 연사는 최신 기계에서 주소 변환이 작동하는 방식에 대해 논의하고 C 및 C++ 프로그래밍의 스택 개념에 대해서도 자세히 설명합니다. 스택은 함수 호출 및 지역 변수를 추적하고 선형 순서를 따르는 데 사용됩니다. 화자는 전통적인 선형 스택에서 포인터의 한 가지 규칙을 강조합니다. 부모는 스택 변수에 대한 포인터를 자식에게 전달할 수 있지만 변수를 덮어쓰는 것을 방지하기 위해 다른 방법으로는 전달할 수 없습니다. 발표자는 또한 메모리를 하위 함수에서 상위로 다시 전달하기 위해 힙 또는 상위 스택에 메모리를 할당하는 것과 같은 옵션을 제안합니다.
00:20:00 병렬 힙 할당이 정확합니다. 힙 기반 cactus 스택을 사용할 때 잠재적인 문제는 메모리 조각화입니다. 여기서 향후 할당을 위해 남아 있는 연속 메모리가 충분하지 않아 공간이 낭비되고 잠재적으로 부족해질 수 있습니다. 메모리 또는 프로그램 충돌. 병렬 프로그래밍을 위한 초기 시스템에서 이 전략을 사용했지만 성능에 미치는 영향을 최소화하고 메모리 단편화의 결과를 고려하기 위해 코드를 최적화하는 것이 중요합니다.
00:25:00 이 섹션에서 비디오는 최대 깊이에 상한을 두지 않고 스택 프레임을 할당하기 위해 힙 기반 선인장 스택 접근 방식을 사용하는 방법에 대해 설명합니다. 그러나 이 힙 기반 선인장 스택으로 기존의 선형 스택 코드를 사용하려고 할 때 상호 운용성이 문제입니다. 이는 스레드 로컬 메모리 매핑이라는 접근 방식을 사용하여 수정할 수 있지만 이 접근 방식에는 운영 체제를 변경해야 합니다. 그럼에도 불구하고 힙 기반 cactus 스택 접근 방식은 여전히 실용적이며 이를 사용하는 Silk 프로그램의 공간 제한을 증명하는 데 사용할 수 있습니다. 이 공간 제한은 힙 기반 선인장 스택을 사용하는 P 작업자 실행의 스택 공간이 P 곱하기 s1로 상한이 있음을 보여줍니다. 여기서 s1은 실크 프로그램의 직렬 실행에 필요한 스택 공간입니다. 이것은 힙 기반 선인장 스택 접근 방식의 좋은 기능입니다.
00:30:00 이 섹션에서는 분할 정복 행렬 곱셈 코드를 분석하여 시공간 교환 정리에 어떻게 적용할 수 있는지 이해합니다. 이 코드는 각각 크기가 N/2인 8번의 재귀 호출을 수행하고 각 호출 전에 malloc을 수행하여 N 제곱 크기의 임시 공간을 얻은 다음 함수가 반환되기 직전에 해제합니다. 할당은 스택 규율을 따르므로 힙을 할당하는 경우에도 이전 슬라이드에서 바인딩된 공간을 P 작업자 공간의 상한으로 사용할 수 있습니다. 작업은 N 세제곱이고 스팬은 오더 로그 제곱 N입니다. 공간에 대한 반복은 N/2의 s + N 제곱의 세타이며, N 제곱으로 풀립니다. 따라서 제한된 공간에 대한 바쁜 잎 속성 및 정리는 P 프로세서에서 공간이 P 곱하기 N 제곱으로 제한됨을 보여줍니다.
00:35:00 이 섹션에서 연사는 이전 섹션에서 논의된 알고리즘에 대한 더 강력한 공간 경계를 증명하는 방법을 통해 청중을 안내합니다. 알고리즘의 구조를 분석하고 재귀 트리의 상단 근처에서 가능한 한 많이 분기하는 데 집중함으로써 화자는 P의 공간 경계를 N의 1/3 곱하기 이전 상한보다 더 나은 것으로 입증할 수 있습니다. . 발표자는 알고리즘의 구조를 분석하면 단순히 일반 정리를 적용하는 것보다 더 강력한 공간 제한 증명으로 이어질 수 있다고 지적합니다. 이 섹션은 병렬 기능이 레거시 및 타사 직렬 바이너리와 상호 운용되지 않는 방법에 대해 설명하면서 결론을 내립니다.
00:40:00 이 섹션에서 연사는 레거시 코드용 스택 풀을 유지 관리하는 데 사용할 수 있는 저장소 할당의 선형 스택 풀 사용에 대해 논의합니다. 풀의 스택 수는 제한된 공간이 보존되도록 프로세서 수에 일정하게 곱해야 합니다. 그러나 이 전략은 사용 가능한 스택이 더 이상 없으면 작업자가 훔칠 수 없기 때문에 작업 훔치기 알고리즘의 시간 제한에 영향을 미칠 수 있습니다. 그런 다음 발표자는 할당기 속도 및 사용자 공간을 포함하여 힙 저장소 할당기의 기본 속성에 대해 이야기하면서 조각화 및 할당 오버헤드의 가능성으로 인해 작은 블록에 대한 최적화의 중요성을 강조합니다. 단편화는 할당자 공간을 사용자 공간으로 나눈 것으로 정의됩니다.
00:45:00 비디오의 이 섹션에서 발표자는 할당된 공간을 사용자 공간에 최대한 가깝게 유지하여 둘의 비율을 최소화하는 방법에 대해 논의합니다. 한 가지 해결책은 운영 체제에 메모리의 특정 페이지가 더 이상 필요하지 않지만 가상 메모리에 보관해야 한다고 알려주는 M Advice라는 것을 사용하는 것입니다. 발표자는 또한 빈 자유 목록에 대한 조각화는 U의 오더 로그 베이스 2(U는 할당된 총 메모리 양)라는 이전 강의의 정리를 언급하고 공간 오버헤드, 내부 조각화 및 외부 조각화의 차이점을 설명합니다. 마지막으로 발표자는 최신 64비트 프로세서가 약 2~48바이트의 가상 주소 공간을 제공하며, 이는 대부분의 프로그램에 충분하지만 여전히 일반 시스템의 물리적 메모리보다 더 크다고 말합니다.
00:50:00 이 섹션에서 비디오는 기본 C++ 할당자가 작동하는 방식인 뮤텍스 보호와 함께 전역 힙을 사용하는 병렬 힙 할당 전략을 살펴봅니다. 이 전략의 장점 중 하나는 직렬 할당자와 비교하여 추가 공간이 필요하지 않기 때문입니다. 그러나 이 접근 방식의 잠재적인 문제는 모든 할당 및 할당 해제에 대한 잠금 획득이 느리고 프로세서가 증가함에 따라 악화되기 때문에 성능 저하입니다. 잠금 경합은 낮은 확장성의 주요 원인으로, 더 높은 요청 비율로 인해 작은 할당에 더 문제가 되고 큰 블록 할당에는 더 많은 작업이 필요합니다.
00:55:00 이 섹션에서 비디오는 로컬 힙 접근 방식을 사용할 때 발생할 수 있는 잠재적인 문제에 대해 설명합니다. 즉, 메모리 드리프트 및 무제한 폭발로 이어질 수 있습니다. 기본적으로 모든 메모리를 한 스레드에 할당하고 다른 스레드에서 해제하면 할당자가 재사용할 만큼 똑똑하지 않은 시스템에 사용되지 않은 메모리가 있을 수 있습니다. 결과적으로 다중 프로세서에서 실행되는 프로그램은 결국 메모리가 부족할 수 있지만 단일 코어에서만 실행되는 경우에는 발생하지 않습니다. 비디오는 이 문제를 해결하기 위해 빈 자유 목록 접근 방식을 사용할 것을 제안합니다. 여기에는 해제된 블록이 연결된 목록 중 하나에 나타날 수 있도록 빈 자유 목록 데이터 구조에 포인터를 설정하는 것이 포함됩니다. 또 다른 전략은 메모리를 주기적으로 재조정하는 것이지만 더 간단한 접근 방식도 설명합니다.
01:00:00 이 섹션에서는 비디오에서 메모리 할당자를 변경하여 각 스레드가 전역 힙 없이 자체 힙에 액세스하도록 하는 원하는 동작을 달성하는 방법에 대해 설명합니다. 한 가지 방법은 소유자로 각 개체에 레이블을 지정하고 해제되면 소유자의 힙으로 반환하는 것입니다. 이러한 방식으로 로컬 개체는 빠르게 할당 및 해제되는 반면 원격 개체는 약간의 동기화가 필요하지만 전역 힙만큼은 아닙니다. 할당할 수 있는 최대 메모리 양은 순차 프로그램에서 사용하는 양인 X로 제한되며, 확대 비율은 힙 수인 P로 상한이 지정됩니다. 이 접근 방식은 또한 여러 프로세서가 서로 다른 메모리 위치에 액세스하지만 동일한 캐시 라인에 있을 때 발생하는 잘못된 공유에 대한 복원력이 있습니다.
01:05:00 이 섹션에서 발표자는 병렬 힙 할당이 잘못된 공유로 이어질 수 있는 방법에 대해 논의하고 비축 할당자를 솔루션으로 소개합니다. 저장 할당자는 로컬 및 전역 힙의 조합을 사용하여 메모리를 힙 간에 이동할 수 있는 대형 수퍼 블록으로 구성합니다. 이 접근 방식은 빠르고 확장 가능하며 잘못된 공유에 대해 탄력적입니다. 할당이 이루어지면 할당자는 로컬 힙에서 사용 가능한 개체를 확인하고 존재하는 경우 가져옵니다. 그렇지 않은 경우 더 많은 메모리를 얻기 위해 전역 힙으로 이동합니다.
01:10:00 이 섹션에서 발표자는 Horde 할당자가 슈퍼 블록의 움직임을 조밀화하기 위해 가장 가득 찬 비 전체 슈퍼 블록에서 자유 개체를 할당하여 외부 조각화를 줄이는 방법을 설명합니다. 로컬 힙에서 객체가 발견되지 않으면 글로벌 힙을 확인하고, 글로벌 힙이 비어 있으면 OS에서 새로운 수퍼 블록을 호출합니다. Horde 할당자는 힙이 최대 절반만 사용되는 불변성을 유지하며, 힙이 충분히 사용되지 않는 것을 감지하면 반쯤 비어 있는 수퍼 블록을 전역 힙으로 이동합니다. 그런 다음 발표자는 전역 힙에 할당된 최대 저장소가 로컬 힙에 할당된 최대 저장소임을 나타내는 기본형을 제시합니다. 마지막으로 화자는 Horde 할당자의 풋프린트가 순서 u + SP에 의해 상한이라는 정리를 증명합니다. 여기서 u는 프로그램의 사용자 풋프린트이고 SP는 로컬 힙에서 할당되었지만 사용되지 않은 스토리지입니다. 폭발은 1 더하기 차수 SP를 u로 나눈 값으로 계산됩니다.
01:15:00 이 섹션에서 발표자는 Je malloc 및 Super malloc을 비롯한 다양한 할당자에 대해 설명합니다. Je malloc은 다른 할당 크기에 대해 별도의 전역 잠금을 가지고 있으며 다른 할당 추적에 강력하게 만드는 em 어드바이스를 사용하여 빈 페이지를 해제합니다. 반면에 Super malloc은 코드 라인이 매우 적고 매우 빠르게 발전하고 있습니다. 화자는 Super malloc이 Horde보다 더 나은 J malloc보다 더 나은 성능을 보인 반면 기본 할당자는 성능이 좋지 않은 벤치마크 결과를 공유합니다. 토론은 또한 가비지 수집으로 확장되지만 연사는 이에 대한 세부 사항을 온라인 슬라이드로 연기합니다.
Cilk 런타임 시스템은 무작위 작업 도용 스케줄러를 사용하여 런타임 시 프로세서에 계산을 매핑하여 병렬 프로세서에서 계산을 예약하고 로드 밸런싱하는 역할을 합니다. 이 시스템은 도용에 대한 추가 비용이 발생하더라도 프로그램의 직렬 실행을 최적화하도록 설계되었습니다. 작업자는 스택 프레임에 대한 포인터를 포함하고 헤드 및 테일 포인터를 사용하는 별도의 데크 데이터 구조를 유지합니다. 훔칠 수 있는 프레임에는 데크가 호출 스택 외부에 있는 동안 훔치는 데 필요한 정보가 포함된 추가 로컬 구조가 있습니다. 이 섹션에서는 시스템이 프로세서가 실행 중인 함수의 중간에서 실행을 시작할 수 있도록 하는 방법과 특정 프로세서가 여전히 계산이 완료되기를 기다리고 있기 때문에 지점을 넘어 실행할 수 없는 동기화 문에 도달할 때 프로세서 간의 동기화가 복잡해지는 방법을 설명합니다. 또한 발표자는 시스템의 성능, 설계 고려 사항 및 데이터 구조, 시스템이 THC 프로토콜을 사용하여 실행을 최적화하는 방법에 대해 설명합니다. 여기에는 작업을 실행하는 작업자와 도둑을 위한 두 가지 프로토콜 세트가 포함됩니다.
Cilk Runtime System은 set jump 및 long jump 프로토콜을 사용하여 희생 프로세스의 실행 데크에서 계산 도용을 처리합니다. 캑터스 스택 추상화는 도둑 프로세스가 피해자 스택의 손상을 방지하기 위해 자체 호출 스택을 가질 수 있도록 합니다. 시스템의 동기화 프로토콜은 계산 트리와 Cactus 스택을 사용하여 동기화가 함수 내의 중첩된 계산 사이에서만 발생하도록 합니다. 전체 프레임 트리는 동기화 프로세스를 단순화하기 위해 뛰어난 하위 계산이 있는 계산 간의 부모-자식 관계를 유지합니다. 또한 런타임 시스템은 현재 함수에 미해결 자식 계산이 없고 모든 작업자가 바쁜 일반적인 경우를 최적화합니다. 지원되는 다른 기능으로는 C++ 예외, 감속기 하이퍼 개체 및 혈통이 있습니다.
00:00:00 이 섹션에서 Tibi는 병렬 프로세서에서 계산을 예약하고 로드 밸런싱하는 Cilk 런타임 시스템에 대해 설명합니다. 런타임 시스템은 무작위 작업 도용 스케줄러를 사용하여 런타임 시 프로세서에 계산을 매핑하여 효율적인 실행을 보장합니다. Tibi는 Cilk 런타임 시스템이 복잡한 소프트웨어이지만 Cilk 컴파일러와 런타임 라이브러리의 협력을 통해 근본적인 마법이 구현된다고 말합니다. 또한 그는 컴파일 후 간단한 Cilk 프로그램에 대한 의사 코드를 보여주며 Cilk 런타임 시스템의 기본이 되는 복잡한 프로세스를 강조합니다.
00:05:00 이 섹션에서 연사는 Cilk 런타임 시스템에 필요한 기능과 성능 고려 사항을 설명합니다. 그는 병렬화된 피보나치 루틴의 예를 사용하여 Cilk 프로그램이 하나의 프로세서에서 프로그램이 실행될 때 동적으로 펼쳐지는 계산 dag를 실행하는 방법을 설명합니다. 그러나 silk spawn 문을 만나면 fib 3에 대해 새 프레임이 생성되고 다른 가닥을 병렬로 실행할 수 있습니다. 그런 다음 프로세서는 일반 함수 호출인 것처럼 fib 3을 실행하기 시작합니다. 명령 포인터가 fib 루틴의 시작 부분으로 돌아갈 때 프로세스가 반복됩니다.
00:10:00 이 섹션에서는 여러 프로세서가 Cilk 런타임 시스템의 도움을 받아 fib 루틴을 병렬로 실행하는 방법을 살펴봅니다. 각 프로세서는 독립 레지스터가 있음에도 불구하고 실행 기능의 중간으로 이동하여 실행을 시작합니다. 이는 실크 시스템이 프로세서가 실행 기능의 중간에서 실행을 시작할 수 있도록 하는 방법에 대한 의문을 제기합니다. 또한 특정 프로세서가 여전히 계산이 완료되기를 기다리고 있기 때문에 지점을 넘어 실행할 수 없는 동기화 문에 도달하면 프로세서 간의 동기화가 복잡해지며 중첩된 패턴 내에서 미세한 동기화가 필요합니다.
00:15:00 이 섹션에서 발표자는 Cilk 런타임 시스템의 구현 고려 사항에 대해 논의합니다. 그들은 세 가지 주요 고려 사항을 언급합니다. 단일 작업자가 프로그램을 실행할 수 있어야 함, 실행 기능 중간에 뛰어들어 다른 프로세서가 중단한 부분을 선택할 수 있는 기능, 동기화. 또한 Silk에는 스택의 모든 보기를 사용 가능하고 일관되게 만들기 위해 올바르게 구현해야 하는 선인장 스택의 개념이 있습니다. 마지막으로 시스템은 프로세서가 서로 프레임을 훔칠 수 있도록 하여 작업 도용을 허용해야 합니다.
00:20:00 이 섹션에서 연사는 Cilk Runtime System에 필요한 기능에 대해 논의합니다. 여기에는 직렬 실행, 기능 실행 중간에 뛰어드는 도둑, 중첩된 미세한 방식으로 동기화하기 위한 동기화, 모든 작업자가 볼 수 있고 스폰 프레임과 계산을 도용할 때 사용할 수 있는 호출된 프레임의 혼합을 처리합니다. 그런 다음 이 섹션은 충분한 병렬 처리가 필요한 시스템의 성능을 다루기 위해 이동합니다. T1 over T 무한대는 P보다 훨씬 커야 하며 프로그램을 실행하기 위해 프로세서 수를 늘릴 때 선형 속도 향상을 원합니다. 이 섹션에서는 또한 P 프로세서에서 TCP의 예상 실행 시간을 다룹니다. 이는 계산 작업을 프로세서 수로 나눈 값에 계산 범위 정도의 값을 더한 값에 비례합니다.
00:25:00 이 섹션에서는 Cilk 런타임 시스템과 충분한 병렬 처리가 있는 프로그램에서 높은 작업 효율성을 유지하려는 목표에 대해 알아봅니다. 실크 런타임 시스템은 강철에 약간의 추가 비용을 지불하더라도 프로그램의 직렬 실행을 최적화하여 작업 우선 원칙을 준수합니다. 런타임 시스템 라이브러리는 병렬 실행 문제를 처리하고 강철이 발생할 때 더 느린 실행 경로를 처리합니다. 작업자는 스택 프레임에 대한 포인터를 포함하고 헤드 및 테일 포인터를 사용하는 별도의 데크 데이터 구조를 유지합니다. 훔칠 수 있는 프레임에는 데크가 호출 스택 외부에 있는 동안 훔치는 데 필요한 정보가 포함된 추가 로컬 구조가 있습니다.
00:30:00 이 섹션에서는 Cilk 런타임 시스템의 디자인과 기본 데이터 구조에 대해 알아봅니다. 시스템은 각 계산에 대한 스폰 헬퍼 함수를 생성하며, 스폰 함수 및 스폰 헬퍼의 각 인스턴스화에 대한 작업자 구조 및 실크 스택 프레임 구조를 각각 유지합니다. Silk RTS 스택 프레임에는 Silk 스택 프레임의 상태를 요약하는 버퍼 및 플래그 정수와 같은 필드와 호출 스택의 부모 Silk 스택 프레임에 대한 포인터가 포함되어 있습니다. 작업자 구조는 데크와 현재 실크 RTS 스택 프레임에 대한 포인터를 유지합니다. 이러한 데이터 구조는 Intel so+ 런타임 시스템이 자세히 설명하는 Cilk 런타임 시스템의 필수 요소입니다.
00:35:00 이 섹션에서는 동영상에서 스폰 함수 "foo" 및 스폰 헬퍼 함수에 대한 코드를 살펴봅니다. "foo"에 대한 코드에는 스택 프레임을 초기화하는 호출, 설정된 점프 루틴을 사용하여 스폰에 대해 설정, 스폰 헬퍼 함수 "spawn bar"에 대한 호출, Silk RTS의 싱크에 대한 조건부 코드 블록, 정리를 위해 팝 및 리프 프레임을 호출합니다. 스폰 헬퍼의 코드에는 스택 프레임을 초기화하는 호출과 스택 구조에 대한 추가 정리 기능을 사용하여 Silk RTS를 분리하는 호출이 포함됩니다. 설정 루틴은 기능 위치를 다시 시작하는 데 필요한 정보를 저장하는 버퍼를 인수로 취하여 도둑이 기능의 연속을 훔칠 수 있도록 하는 기능으로 설명됩니다.
00:40:00 이 섹션에서 발표자는 레지스터 집합을 제한하고 함수 호출을 위해 미리 결정된 집합에 레지스터를 저장하는 방법에 대해 설명합니다. 레지스터를 저장하는 책임은 함수에 있지만 명령어 포인터와 스택 포인터는 버퍼에 저장됩니다. 이 섹션에서는 계속해서 스폰 헬퍼 함수와 작업자 구조 및 현재 스택 프레임을 업데이트하는 방법에 대해 설명합니다. 마지막으로 이 섹션에서는 빠른 프레임 입력 루틴이 호출 스택에서 상위 포인터를 설정하고 작업자의 현재 스택 프레임을 맨 아래를 가리키도록 업데이트하는 방법을 설명합니다.
00:45:00 이 섹션에서는 "The Cilk Runtime System"이라는 제목의 YouTube 동영상 스크립트에서 Silk RTS 분리 기능이 계산을 도난당하도록 허용하는 방법을 설명합니다. 여기서 실크 예술 실행이 완료되면 도둑이 와서 훔칠 수 있습니다. 실크 산란의 지속. 팝 프레임은 스택 프레임 구조를 정리하고 부모를 가리키도록 현재 스택 프레임을 업데이트하는 역할을 합니다. 이 함수 호출은 반환될 수도 있고 반환되지 않을 수도 있으며, 이 두 가지 경우 중 런타임 시스템이 최적화하는 데 더 중요한 것은 두 가지 작동 첫 번째 원칙을 기반으로 한 성공 사례입니다.
00:50:00 이 섹션에서 발표자는 작업자가 정기적인 직렬 실행을 수행한다고 가정하는 경우 1의 작업자 실행에 대한 Cilk 런타임 시스템의 최적화에 대해 설명합니다. 그들은 또한 도둑이 피해자의 데크 상단을 목표로 하고, 항목을 대기열에서 빼내고, 데크의 헤드와 현재 스택 프레임 포인터를 업데이트하는 등 작업자 도둑질이 어떻게 작동하는지 설명합니다. 생성된 함수의 결과는 원래 SIL 코드의 상위 스택 프레임으로 반환됩니다.
00:55:00 이 섹션에서 연사는 THC 프로토콜이라는 프로토콜을 사용하여 여러 프로세서와 관련된 동시 액세스를 처리하는 Cilk 런타임 시스템의 접근 방식을 설명합니다. 프로토콜에는 작업을 수행하는 작업자와 도둑을 위한 두 가지 프로토콜 집합이 포함됩니다. 작업자의 프로토콜은 데크 바닥에서 무언가를 터뜨리려고 시도함으로써 최적화되며, 실패 시에만 데크의 자물쇠를 획득하는 반면, 도둑은 항상 데크 작업을 수행하기 전에 자물쇠를 잡습니다. 그런 다음 도둑은 멀리뛰기 함수를 호출하고, 설정된 점프 함수에서 검색된 스택 프레임 버퍼를 전달하고, 등록 상태를 훔친 속편의 레지스터 상태로 설정하여 마법처럼 훔친 속편을 다시 시작합니다.
01:00:00 이 섹션에서 연사는 Cilk 런타임 시스템 내에서 세트 점프와 멀리뛰기 호출 간의 상호 작용에 대해 설명합니다. 그들은 멀리뛰기 루틴이 호출될 때 세트 점프에서 두 번째로 효과적으로 반환하는 방법을 설명합니다. 이번에는 두 번째 인수에 지정된 다른 값을 사용합니다. 적절한 버퍼와 두 번째 인수를 사용하여 도둑은 피해자 코드의 특정 계산을 건너뛰기 위해 멀리뛰기를 실행할 수 있습니다. 발표자는 호출을 건너뛰고 다른 접근 방식을 사용하는 데 필요한 거리를 정적으로 계산하는 것이 가능하지만 설정된 점프 및 멀리뛰기 프로토콜이 Cilk 런타임 시스템을 위한 보다 유연한 방법 역할을 한다고 말합니다. 전체적으로 스피커는 도둑이 Cilk를 사용하여 피해자의 데크에서 계산을 훔치기 위해 사용할 수 있는 다양한 기술을 강조합니다.
01:05:00 이 섹션에서는 Cilk 런타임 시스템에 대한 선인장 스택 추상화의 필요성에 대해 설명합니다. 피해자의 스택을 사용하면 피해자의 스택이 손상될 수 있고 모든 작업자에 걸쳐 일관성을 유지하는 데 문제가 발생할 수 있다고 설명합니다. 따라서 도둑에 대한 별도의 호출 스택이 필요합니다. Cactus 스택의 구현에는 RB p의 오프셋을 통해 희생자의 스택에 있는 함수의 상태에 계속 액세스할 수 있는 동안 도둑이 컨티뉴에이션을 훔치고 스택 포인터를 자신의 스택으로 설정하는 것이 포함됩니다.
01:10:00 이 섹션에서 발표자는 SIL 런타임 시스템이 서로 다른 프로세서에서 계산 동기화를 처리하는 방법을 설명합니다. 시스템은 선인장 스택과 계산 트리를 사용하여 일반적으로 프로그램이 아닌 함수 아래에 중첩된 하위 계산 사이에서만 동기화가 발생하도록 합니다. 작업자가 모든 하위 계산이 반환되기 전에 실크 동기화 문에 도달하면 도둑이 되어 도난당한 계산의 스택 프레임에서 작업을 계속합니다. 이를 통해 시스템은 작업자 낭비를 방지하고 중첩 계산이 적절하게 동기화되도록 할 수 있습니다. 시스템은 특히 이 접근 방식과 충돌할 수 있는 최적화를 사용하지 않도록 컴파일러에 지시합니다.
01:15:00 이 섹션에서 Cilk 런타임 시스템은 전체 프레임이라는 상태 트리를 유지 관리하는 것으로 설명되며, 어떤 계산이 완료되기를 기다리고 있는지 추적합니다. 이 시스템은 전체 프레임 트리를 사용하여 상위 프레임에 대한 포인터, 잠재적으로 하위 프레임에 대한 포인터 및 뛰어난 하위 계산이 서로 어떻게 관련되어 있는지를 포함하여 병렬 실행을 위한 많은 정보를 추적합니다. 작업자가 동기화를 만났을 때 처리되지 않은 자식 계산이 있는 경우 동기화할 수 없으며 도둑이 되어 더 많은 작업을 훔칠 수 있을 때까지 전체 프레임을 일시 중단해야 합니다. 이 시스템은 프로그램이 충분한 병렬성을 가질 수 있도록 하고 동기화 프로토콜을 단순화합니다.
01:20:00 이 섹션에서 연사는 Cilk Runtime System이 실행 함수에 뛰어난 자식이 없고 시스템의 모든 작업자가 각자의 작업으로 바쁜 일반적인 경우를 최적화하는 방법에 대해 설명합니다. 런타임 시스템은 연결된 스택 프레임의 플래그 필드의 비트를 사용하여 실크 동기화에 동기화가 필요한지 여부를 평가합니다. 발표자는 또한 C++ 예외, 리듀서 하이퍼 개체 및 혈통을 포함하여 런타임 시스템에서 지원하는 몇 가지 다른 기능에 대해서도 언급합니다.
캐싱 및 캐시 효율적인 알고리즘에 대한 비디오에서 강사는 최신 시스템의 캐시 계층 구조, 완전 연관 캐시와 직접 매핑 캐시의 차이점, 세트 연관 캐시의 장단점을 설명합니다. 비디오는 또한 이상적인 캐시 모델과 캐시 효율적인 알고리즘의 개념을 소개합니다. 발표자는 캐시 미스 기본형, tall형 캐시 가정 및 하위 행렬 캐싱 기본형에 대해 설명합니다. 또한 하위 행렬을 읽을 때와 행렬 곱셈 중에 발생한 캐시 미스를 분석합니다. 비디오는 타일 행렬 곱셈의 개념과 성능을 크게 향상시킬 수 있는 방법을 소개하면서 결론을 내리지만, 이식성이 없으며 여러 수준의 캐시에 대해 최적화하는 데 비용이 많이 들 수 있다는 점도 언급합니다.
강의에서는 재귀 행렬 곱셈을 예로 들어 캐싱 및 캐시 효율적인 알고리즘을 다룹니다. 발표자는 작업 및 캐시 미스를 개별적으로 분석하는 것의 중요성을 강조하고 캐시 인식 알고리즘이 캐시 크기가 다르기 때문에 모든 시스템에 최적이 아닐 수 있음을 언급합니다. 발표자는 또한 모든 캐시 크기에 맞게 자동 조정되는 캐시 무시 알고리즘에 대해 논의하고 병렬 캐시 무시 코드의 개발을 언급합니다. 마지막으로 목표는 캐시를 인식하거나 캐시를 무시하는 알고리즘을 설계하는 것이며 캐시를 무시하는 알고리즘 설계에 대한 논의는 다음 강의에서 계속됩니다.
00:00:00 캐싱 및 캐시 효율적인 알고리즘에 대한 이 섹션에서 강사는 각 프로세서에 대한 개인 L1 데이터 및 명령 캐시, 개인 L2 캐시 및 마지막 레벨 캐시를 포함하는 최신 시스템의 캐시 계층 구조에 대해 설명합니다. 모든 프로세서 간에 공유됩니다. 이러한 캐시의 크기는 메모리 계층이 올라갈수록 증가하며 DRAM이 가장 느리고 가장 큽니다. 캐시와 대기 시간의 연관성은 메모리 계층 구조가 올라갈수록 증가하며 L1 캐시가 가장 빠르고 연관성이 높습니다. 또한 강사는 병렬 처리를 위한 메모리 주소 액세스의 일관성을 보장하기 위한 캐시 일관성 프로토콜의 중요성에 대해서도 언급합니다. 프로그램에서 지역성을 활용하는 방법을 이해하면 더 빠른 메모리 캐시를 효율적으로 사용하는 데 도움이 될 수 있습니다.
00:05:00 이 섹션에서는 완전 연관 캐시와 직접 매핑 캐시 간의 차이점에 대해 설명합니다. 완전 연관 캐시는 블록을 찾기 위해 여러 라인에 액세스해야 할 수 있으므로 느리고 비효율적일 수 있는 블록을 찾기 위해 전체 캐시를 검색해야 합니다. 반면에 직접 매핑된 캐시는 각 블록에 대해 가능한 위치가 하나만 있으므로 충돌이 적고 블록에 훨씬 빠르게 액세스할 수 있습니다. 캐시 블록의 위치를 결정하기 위해 가상 메모리 주소를 나눌 때 주소 공간의 세 가지 구성 요소인 오프셋, 세트 및 태그도 설명됩니다. 태그는 캐시 블록이 해당하는 메모리 블록을 식별하고 세트는 블록이 들어가는 캐시의 위치를 결정하며 총 주소 공간은 W 비트입니다.
00:10:00 이 섹션에서는 비디오에서 캐시의 한 위치만 검색하면 되기 때문에 빠르지만 캐시 블록이 계속 서로를 제거하는 충돌 누락이 발생하기 쉬운 직접 매핑된 캐시의 장단점에 대해 설명합니다. 성능 저하. 그런 다음 비디오는 각 세트에 여러 라인이 포함되어 각 캐시 블록에 대해 캐시에서 둘 이상의 가능한 위치를 허용하는 하이브리드 솔루션인 세트 연관 캐시를 소개합니다. 비디오는 또한 캐시 블록에 처음 액세스할 때 발생하고 피할 수 없는 콜드 미스를 포함하여 다양한 유형의 캐시 미스에 대한 분류를 언급합니다.
00:15:00 이 섹션에서 비디오는 용량 미스, 충돌 미스 및 공유 미스를 포함하여 다양한 유형의 캐시 미스에 대해 설명합니다. 용량 미스는 캐시가 가득 차서 액세스해야 하는 모든 캐시 블록을 맞출 수 없을 때 발생하는 반면, 충돌 미스는 동일한 집합의 너무 많은 블록이 캐시에 매핑될 때 집합 연관 캐시에서 발생합니다. 마지막으로 공유 미스는 병렬 컨텍스트에서 여러 프로세서가 동일한 캐시 라인에 액세스하고 그 중 적어도 하나가 쓰기 작업을 수행할 때 발생합니다. 비디오는 또한 행 주요 순서로 저장된 더 큰 행렬 내의 하위 행렬에 액세스할 때 충돌 누락에 대한 나쁜 사례의 예를 제공합니다.
00:20:00 이 섹션에서 발표자는 캐싱 및 캐시 효율적인 알고리즘에 대해 설명합니다. 그들은 더 큰 행렬 내에서 하위 행렬에 액세스하는 예와 캐시가 4방향 연관만 있을 때 충돌 누락이 발생할 수 있는 방법을 사용합니다. 발표자는 매트릭스의 각 행 끝에 일정한 양의 공간을 추가할 것을 제안하므로 각 행은 2^15바이트보다 길어 충돌 누락을 줄이는 데 도움이 될 수 있습니다.
00:25:00 이 섹션에서 발표자는 알고리즘의 캐시 성능을 분석하는 데 사용되는 모델인 이상적인 캐시 모델에 대해 논의합니다. 이 모델은 2단계 캐시 계층, 완전 연관 캐시 및 최적의 Nishant 교체 정책을 가정합니다. 연사는 중요한 두 가지 성능 측정이 N의 차수와 캐시 미스 횟수라고 설명합니다. 여기서 이상적인 시나리오는 기존 표준 알고리즘의 작업을 늘리지 않고 캐시 미스 횟수를 줄이는 것입니다. 1985년에 입증된 LRU 보조정리도 언급되는데, 이는 M 크기의 이상적인 캐시에서 Q 캐시 미스를 발생시키는 알고리즘이 LRU 정책을 사용하는 크기 2M의 완전 연관 캐시에서 2Q 캐시 미스를 발생시킨다는 것을 나타냅니다.
00:30:00 이 섹션에서 발표자는 캐시 효율적인 알고리즘의 개념과 캐시 미스 수를 최소화하여 프로그램 성능을 향상시키는 방법을 소개합니다. 그는 최소 최근 사용(LRU) 교체 정책에 대해 설명합니다. LRU를 사용하는 이상적인 캐시 크기의 두 배인 완전 연관 캐시는 캐시 미스 횟수의 두 배를 넘지 않도록 합니다. 이를 통해 점근 분석을 수행할 때 캐시 미스를 보다 쉽게 분석할 수 있습니다. 발표자는 또한 캐시 미스 보조 정리를 제시하여 프로그램이 크기가 캐시 크기의 1/3 미만이고 평균 크기가 적어도 캐시 라인 크기인 데이터 세그먼트 집합을 읽는다면 모두 읽기 위한 캐시 미스는 세그먼트의 총 크기를 캐시 라인의 크기로 나눈 최대 3배입니다.
00:35:00 이 섹션에서 비디오는 캐싱과 관련된 두 가지 가정인 캐시 미스 기본형 및 높은 캐시 가정에 대해 설명합니다. 캐시 미스 기본형은 데이터 세그먼트의 평균 길이가 캐시 블록 크기보다 크면 캐시 미스 수가 상수만큼만 증가한다고 말합니다. 키가 큰 캐시 가정은 캐시가 너비보다 키가 크다고 가정하며 일반적으로 실제로 충족됩니다. 비디오는 또한 부분 행렬을 캐시 라인에 맞출 때 짧은 캐시와 관련된 문제와 tall 캐시 가정이 이 문제를 해결하는 데 유용한 이유에 대해 설명하는 부분 행렬 캐싱 기본형에 대해 설명합니다.
00:40:00 이 섹션에서 발표자는 캐싱 및 캐시 효율적인 알고리즘에 대해 설명합니다. 정방형 하위 행렬을 캐시로 읽을 때 발생하는 캐시 미스 수를 분석하고 캐시 미스 정리를 사용하여 행렬의 모든 요소를 캐시로 읽어들이는 데 필요한 캐시 미스 수가 최대 3n^2/B임을 보여줍니다. . 그런 다음 행렬이 행 주요 순서이고 tall 캐시 가정을 충족한다고 가정하여 표준 3차 작업 행렬 곱셈 알고리즘에서 발생한 캐시 미스 수를 분석합니다. 그들은 세 가지 경우를 고려하고 두 번째와 세 번째 경우에 대해 LRU를 가정하여 궁극적으로 알고리즘 설계에서 캐시 최적화의 중요성을 보여줍니다.
00:45:00 이 섹션에서 발표자는 캐싱 및 캐시 효율적인 알고리즘에 대해 설명합니다. 그들은 행렬 곱셈에 대해 두 가지 경우를 분석합니다. 여기서 n은 B보다 M보다 크고 n은 B보다 C 곱하기 M보다 작습니다. 그들은 LRU 교체 정책을 사용하고 행렬 B에 액세스할 때 발생하는 캐시 미스 수를 계산합니다. 첫 번째에서 경우에, 그들은 n 세제곱 캐시 미스의 세타가 필요하다는 것을 알게 되고, 그 결과 알고리즘에 지역성을 갖는 것으로부터 얻는 것이 없습니다. 두 번째 경우에는 공간적 지역성을 활용하고 캐시 미스 수를 B만큼 줄일 수 있으므로 B 캐시 미스의 세타 세타를 세제곱하여 더 효율적입니다.
00:50:00 비디오의 이 섹션에서 발표자는 캐싱 및 캐시 효율적인 알고리즘에 대해 설명합니다. 그들은 먼저 전체 행렬이 캐시에 맞는 경우를 분석하여 B에 대한 세타 n의 제곱의 총 캐시 미스 수를 생성합니다. 그런 다음 내부 두 루프의 순서를 바꿔서 최적화에 대해 논의합니다. 캐시 미스의 총 수를 B를 세제곱한 n의 세타로 줄입니다. 그러나 그들은 타일링이라는 최적화를 사용하여 더 나은 작업을 수행할 수 있다는 점에 주목합니다. 여기서 6개의 for 루프는 타일을 반복하는 데 사용되며 계산은 각 하위 항목에 대해 수행됩니다. -다음으로 이동하기 전에 매트릭스. 크기가 s x s인 부분행렬에 대한 작업은 s의 세제곱입니다.
00:55:00 이 섹션에서는 타일 행렬 곱셈의 개념을 소개하고 자세히 설명합니다. 이 알고리즘의 목표는 모든 계산이 더 이상 캐시 미스 없이 캐시에서 수행될 수 있도록 하위 행렬을 캐시에 맞추는 것입니다. 캐시 미스 수를 분석한 결과 캐시 미스 수는 n/s^3 곱하기 s^2 /B, 총 n^3/B * sqrt(M) 캐시 미스에 대해 발견되었습니다. 이 숫자는 행렬 곱셈 코드의 성능을 향상시키는 데 매우 중요합니다. 그러나 알고리즘에 문제가 발생합니다. 알고리즘이 실행되는 시스템의 캐시 크기에 크게 의존하기 때문에 이식성이 없습니다. 또한 다차원 조정 최적화는 비용이 많이 들고 여러 수준의 캐시를 최적화할 때 코드가 복잡해집니다.
01:00:00 이 섹션에서 강의는 캐싱 및 캐시 효율적인 알고리즘을 탐구합니다. 발표자는 캐시 효율적인 알고리즘에 대한 매개변수를 조정하고 특정 시스템에 맞게 최적화하는 문제에 대해 논의합니다. 그들은 입력 행렬이 4개의 하위 행렬 또는 사분면으로 나뉘는 재귀 행렬 곱셈 알고리즘을 도입합니다. 출력 행렬의 각 사분면에 대해 두 행렬 곱의 합이 재귀적으로 발생합니다. 마지막으로 화자는 이 알고리즘의 작업을 분석하고 여전히 좋은 캐시 성능을 유지하는 더 단순한 설계라는 결론을 내립니다.
01:05:00 이 섹션에서 발표자는 캐싱 및 캐시 효율적인 알고리즘에 대해 논의하고 매트릭스 곱셈의 예를 사용하여 분석 작업과 캐시 미스의 차이점을 설명합니다. 화자는 재귀 트리를 그려 크기 문제와 분기 하위 문제를 시각화하고 리프까지의 수준 수가 n의 로그 밑수 2라는 점에 주목합니다. 잎의 수는 n의 로그 밑수 2의 8승으로 계산되며, 이는 n의 세제곱과 같습니다. 작업량은 단순히 theta n의 세제곱이며 캐시 미스는 다른 기본 사례로 분석됩니다. 여기서 하위 행렬은 캐시에 적합하고 캐시 미스에 대한 N의 제곱의 세타가 사용됩니다. 발표자는 수준의 수가 n의 로그 밑수 2일 뿐만 아니라 캐시의 크기에 따라 달라지므로 잎의 수가 달라짐을 강조합니다.
01:10:00 이 섹션에서 발표자는 재귀 행렬 곱셈 코드의 예를 사용하여 캐시 효율적인 알고리즘에서 캐시 미스 수를 분석하는 방법을 설명합니다. 코드는 캐시를 무시합니다. 즉, 캐시에 대한 명시적인 지식이 없으며 실행 중인 시스템의 특정 캐시 크기에 대해 수동적으로 자동 조정됩니다. 발표자는 또한 오늘날 최고의 캐시 망각 코드가 임의의 직사각형 행렬에서 작동하고 8방향 분할 대신 이진 분할을 수행한다고 언급합니다. 연사는 병렬 컨텍스트에 대해 논의하고 개인 캐시가 있는 여러 프로세서에서 실행되는 결정론적 셀 계산에서 캐시 미스 수를 분석하는 방법을 설명합니다.
01:15:00 이 섹션에서 발표자는 캐싱 및 캐시 효율적인 알고리즘에 대해 설명합니다. 직렬 착시에서 캐시 미스를 최소화함으로써 기본적으로 낮은 스팬 알고리즘에 대한 병렬 실행에서 캐시 미스를 최소화할 수 있습니다. 스피커는 직렬 실행과 동일한 병렬 재귀 행렬 곱셈 알고리즘에 대한 캐시 미스 바운드를 제공합니다. 목표는 캐시에 대해 명시적으로 알고 있거나 캐시를 인식하지 못하는 알고리즘을 설계하는 것입니다. 발표자는 둘 다의 예를 제공하고 다음 강의에서 캐시 인식 알고리즘 설계에 대한 추가 논의가 있을 것이라고 언급합니다.
이 비디오에서는 머신의 캐시 크기를 자동으로 조정하고 우수한 캐시 효율성을 달성하며 머신의 캐시 매개변수에 대한 지식이 필요하지 않은 캐시 무시 알고리즘에 대해 설명합니다. 영상은 2D 매트릭스에서 스텐실 방법을 사용하여 미분 방정식을 통해 열 확산을 시뮬레이션하는 코드를 작성하는 방법을 보여줍니다. 이 코드에는 루핑 및 사다리꼴 버전이 모두 있으며 후자는 캐시 효율성이 더 높지만 루핑 코드 액세스 패턴의 예측 가능성으로 인해 2D 시뮬레이션에서 훨씬 빠르지는 않습니다. 비디오는 또한 캐싱과 병렬 처리 간의 상호 작용과 잠재적인 병렬 속도 향상 병목 현상 진단에 대해 설명합니다. 마지막으로 발표자는 스텐실 계산과 스텐실이라는 고정 패턴을 사용하여 어레이의 각 포인트가 업데이트되는 방법에 대해 설명합니다. 스텐실은 캐시 누락이 발생할 수 있으며 시간적 및 공간적 지역성을 활용하는 효율적인 알고리즘을 사용하여 스토리지 요구 사항을 줄일 수 있습니다.
비디오의 두 번째 부분에서는 정렬 및 병합을 위한 캐시 인식 알고리즘에 대해 설명합니다. 특히, 비디오는 병합 정렬의 캐시 복잡성을 다루고 다중 방식 병합의 개념을 소개하며 다중 방식 병합 알고리즘의 캐시 복잡성을 설명합니다. 이 동영상에서는 K 제곱 요소와 K 정렬 목록을 병합할 수 있는 캐시 무시 정렬 알고리즘인 깔때기 정렬 알고리즘에 대해서도 설명합니다. 깔때기 정렬 알고리즘은 최적이며 K 깔때기의 제곱근으로 재귀적으로 구성됩니다. 비디오는 b-트리, 순서가 지정된 파일 유지 관리 및 우선 순위 대기열과 같은 다른 많은 캐시 인식 알고리즘 및 데이터 구조가 있다고 설명합니다. 전반적으로 이 비디오는 주제에 대해 자세히 알아보는 데 관심이 있는 사람들을 위해 캐시를 무시하는 알고리즘에 대한 소개를 제공합니다.
00:00:00 이 섹션에서는 비디오에서 캐시 무시 알고리즘에 대해 설명합니다. 이 알고리즘은 시스템의 캐시 크기를 자동으로 조정하고 캐시 매개변수에 대한 지식이 없어도 코드가 우수한 캐시 효율성을 달성하는 알고리즘입니다. 기계. 이 비디오는 미분 방정식을 통해 열 확산을 시뮬레이션하는 예를 사용하여 과학적 컴퓨팅이 종종 미분 방정식에 의존하여 물리적 프로세스를 설명하고 프로세스를 시뮬레이션하기 위해 효율적인 코드를 작성해야 하는 방법을 보여줍니다. 이 비디오는 1D 열 방정식을 시뮬레이션하기 위해 유한 차분 근사법을 기반으로 코드를 작성하는 방법을 보여줍니다.
00:05:00 이 섹션에서 발표자는 스텐실 방법을 사용하여 유한 차분 근사를 허용하는 시뮬레이션 방정식의 코드를 작성하는 방법을 다룹니다. 이 방정식은 T와 X에 대한 U의 편도함수를 사용하며 화자는 근사 방법을 사용하여 이러한 편도함수를 얻는 방법을 보여줍니다. 2D 공간은 X 및 T 값이 각각 가로 및 세로로 표시되는 행렬을 사용하여 표시됩니다. 화자는 행렬의 경계를 설명하고 방정식을 사용하여 U를 계산합니다.
00:10:00 이 섹션에서는 발표자가 과학 컴퓨팅에서 다양한 목적으로 널리 사용되는 방법인 스텐실 계산에 대해 설명합니다. 이 방법에서 배열의 각 지점은 스텐실이라는 고정 패턴을 사용하여 업데이트됩니다. 계산은 세 가지 다른 값에 따라 달라지며 이를 3점 자세라고 합니다. 큰 X 값에 스텐실 계산을 사용할 수 있지만 캐싱과 관련하여 성능이 저하되어 캐시 누락이 발생할 수 있습니다. 또한 포인트 값을 업데이트하기 위해 현재 행과 이전 행의 두 행만 저장하여 데이터 저장에 필요한 저장 공간을 줄일 수 있습니다.
00:15:00 작동: 각 시간 단계에서 이전 행의 값을 사용하여 특정 행의 X 값만 업데이트합니다. 따라서 업데이트할 행과 이전 행으로 사용할 행을 번갈아 사용할 수 있으며 추가 값 행 하나만 유지하면 됩니다. 그러나 이 코드는 캐시 효율성이 높지 않으며 타일링 또는 캐시 인식 알고리즘을 사용하여 더 효율적으로 만들 수 있습니다. 이상적인 캐시 모델은 최적 또는 LRU 교체 정책이 있는 완전 연관 캐시를 가정하고 직렬 실행에서 용량 미스를 캡처하지만 충돌 미스는 캡처하지 않습니다. 그럼에도 불구하고 시간 및 공간 지역성을 활용하는 효율적인 알고리즘을 설계하는 데 여전히 유용합니다.
00:20:00 이 섹션에서 발표자는 외부를 보지 않고 2D 매트릭스에서 사다리꼴 공간 내부의 점을 계산하는 데 캐시 무시 알고리즘을 사용할 수 있는 방법을 설명합니다. 계산에는 X에 대한 UT mod에 대한 포인터를 취하고 W의 0 더하기 알파 곱하기 -1의 W 빼기 2 곱하기 0의 W 더하기 1의 W를 반환하는 커널 함수가 포함됩니다. 캐싱 동작은 LRU 교체 정책을 가정하여 분석됩니다. 캐시 미스의 수는 모든 행에 대해 B보다 NT의 세타입니다. 그러나 화자는 타일링으로 더 나은 성능을 얻을 수 있다고 언급하지만 캐시를 무시하는 버전에 대해 계속 논의합니다. 사다리꼴은 T1에 상단 베이스가 있고 T0에 하단 베이스가 있습니다. 알고리즘은 T, t0, t1, X, x0, x1, DX0, DX1이 포함된 부등식 조건을 사용하여 사다리꼴 내부의 모든 점을 계산합니다. 여기서 DX0 및 DX1은 기울기를 나타내는 -1, 0 또는 1입니다.
00:25:00 이 섹션에서 화자는 사다리꼴 규칙 알고리즘에 대한 분할 정복 접근 방식을 설명합니다. 접근 방식은 사다리꼴의 높이가 1인 기본 사례를 가지며 루프는 계산 순서에 따라 모든 값을 계산합니다. 알고리즘에는 사다리꼴의 너비와 높이에 따라 각각 달라지는 공간 절단과 시간 절단이라는 두 가지 재귀 사례가 있습니다. 사다리꼴이 너무 넓으면 사다리꼴의 중심을 통과하는 기울기가 1 -1 인 선과 함께 사다리꼴이 수직으로 절단되는 공간 절단이 적용됩니다. 반대로 사다리꼴의 키가 너무 크면 타임 컷이 적용되며 중앙을 가로지르는 수평선으로 컷팅됩니다. 재귀 알고리즘은 점 간의 상호 의존성을 방지하기 위해 특정 순서로 사다리꼴의 왼쪽과 오른쪽, 아래쪽과 위쪽을 각각 가로지르는 두 번의 호출을 수행합니다.
00:30:00 이 섹션에서 발표자는 캐시를 무시하는 알고리즘의 캐시 복잡성에 대해 논의합니다. 그들은 재귀 트리 접근법을 분석하고 H가 W의 세타인 HW 포인트의 세타를 나타내는 기본 케이스에 도달할 때까지 알고리즘이 각 레벨에서 두 개의 하위 문제로 나뉜다는 것을 발견했습니다. 리프당 캐시 미스의 수는 세타 W입니다. B 이상이고 잎의 수는 HW보다 NT의 세타입니다. 내부 노드는 캐시 복잡성에 크게 기여하지 않습니다. 캐시 복잡성은 둘 이상의 차원으로 일반화되며 d가 1인 경우 NT over MB가 됩니다.
00:35:00 이 섹션에서 발표자는 루핑 코드와 사다리꼴 코드의 차이점을 설명합니다. 사다리꼴 코드는 캐시 라인의 수인 M의 인수를 저장하여 훨씬 더 나은 캐시 복잡성을 가지고 있습니다. 시뮬레이션은 사다리꼴 코드가 루핑 코드에 비해 더 적은 캐시 미스를 발생시켜 계산을 훨씬 더 빨리 완료함을 보여줍니다. 그러나 발표자는 이 시뮬레이션이 1차원에 대한 것이었고 계속해서 2차원에서 일어나는 일에 대한 데모를 보여줍니다.
00:40:00 이 섹션에서 발표자는 화면의 색상이 온도에 해당하는 2D 공간에서 실시간 열 확산 시뮬레이션을 시연합니다. 발표자는 루핑 코드와 사다리꼴 코드의 성능을 비교하고 사다리꼴 코드가 훨씬 적은 캐시 미스를 발생시키지만 루핑 코드보다 약간 더 빠르다는 것을 보여줍니다. 액세스 패턴이 규칙적이고 예측하기 쉽기 때문에 루핑 코드를 돕는 하드웨어 프리페칭 때문일 수 있습니다.
00:45:00 이 섹션에서 발표자는 캐싱과 병렬 처리 간의 상호 작용에 대해 설명합니다. 그들은 직렬 실행에서 캐시 미스를 최소화하는 것이 낮은 스팬 알고리즘을 가정하여 병렬 실행에서 본질적으로 캐시 미스를 최소화할 수 있다는 정리를 설명합니다. 그런 다음 두 개의 독립적인 사다리꼴이 병렬로 실행되고 회색 사다리꼴이 나중에 실행되는 V 컷을 사용하여 사다리꼴 알고리즘이 어떻게 병렬로 작동하는지 보여줍니다. 역 사다리꼴에 사용되는 거꾸로 된 V 컷도 언급합니다.
00:50:00 이 섹션에서 발표자는 병렬 루핑 코드와 병렬 사다리꼴 코드의 성능을 직렬 코드와 비교하여 설명합니다. 병렬 루핑 코드는 사다리꼴 코드보다 잠재적인 병렬 처리가 더 많음에도 불구하고 잠재적인 속도 향상의 절반 미만을 달성합니다. 이는 메모리 대역폭이 넉넉한 직렬의 경우에 비해 병렬의 경우 메모리 대역폭 병목 현상이 있어 프리페치가 병렬 루핑 코드에 도움이 되지 않기 때문입니다. 대조적으로, 사다리꼴 코드는 선형에 가까운 속도 향상을 달성하는데, 이는 캐시 효율성이 입력 크기에 비해 캐시가 너무 작은 큰 입력 크기에서 훨씬 더 큰 역할을 한다는 사실과 일치합니다.
00:55:00 이 섹션에서 연사는 병렬 속도 향상 병목 현상을 진단하는 방법에 대해 논의하고 불충분한 병렬 처리, 일정 오버헤드, 메모리 대역폭 부족 및 경합과 같은 원인이 될 수 있는 몇 가지 사항을 식별합니다. 그들은 실크 스케일을 사용하여 코드의 병렬성을 측정하고 하드웨어 카운터를 수행하여 메모리 대역폭을 측정하는 것을 포함하여 이러한 문제를 진단하는 여러 가지 방법을 제안합니다. 그러나 경합을 진단하는 것은 특히 어려운 일이며 연사는 경합이 문제인지 평가하기 전에 처음 세 가지 잠재적 원인을 살펴보라고 조언합니다. 마지막으로 발표자는 스텐실 계산에 대해 논의합니다.
01:00:00 이 섹션에서 발표자는 두 개의 정렬된 입력 배열을 병합하는 복잡성을 먼저 분석하여 병합 정렬의 캐시 복잡성을 분석하는 방법에 대해 논의합니다. 이를 수행하는 시간은 입력 배열 크기의 합에 비례합니다. n개의 요소를 병합하는 동안 발생한 캐시 미스의 수는 B의 세타 n입니다. 여기서 B는 캐시 라인의 바이트 수입니다. 병합 정렬에는 절반 크기의 입력에 대한 두 개의 재귀 호출이 있으며 재귀 호출의 정렬된 출력을 병합합니다. 병합 정렬의 전반적인 작업은 n log n의 세타이며 재귀 트리 방법을 사용하여 분석됩니다. 병합 정렬의 캐시 복잡성도 논의되었으며, 캐시 미스의 수는 데이터를 저장하는 데 필요한 캐시 블록의 수에 비례하며, 이는 B log M의 세타(세타 n/B log M, 여기서 M은 최대 크기 a)에 비례함을 보여줍니다. 하위 블록은 가질 수 있습니다.
01:05:00 이 섹션에서 화자는 병합 정렬의 캐시 복잡성에 대한 반복을 설명합니다. 기본 사례는 문제 크기가 캐시에 맞을 때 발생하여 Θ(n/B) 캐시 미스가 발생합니다. 그렇지 않으면 알고리즘에 크기 n/2 및 Θ(n/B) 캐시 미스의 두 재귀 호출이 있어 결과를 병합합니다. 분석에는 n/CM의 로그 밑수 2인 재귀 트리의 수준 수가 포함되며 여기서 CM은 상수입니다. 리프당 캐시 미스 수는 Θ(M/B * n/CM)이며 전체 캐시 미스 수는 Θ(n/B * log (n/CM))이므로 첫 번째 용어에서 B의 계수를 절약합니다. . 그러나 더 큰 문제 크기의 경우 작업과 비교하여 B의 인자만 저장하고 작은 문제 크기의 경우 B log n의 인자를 저장합니다. 화자는 더 나은 해결책이 있는지 묻고 대답은 항상 예입니다.
01:10:00 이 섹션에서 발표자는 정렬된 하위 배열을 병합하기 위해 다중 방식 병합을 사용하는 방법을 설명하고 하위 배열의 최소 요소를 결정하기 위한 토너먼트 트리의 아이디어를 소개합니다. 또한 정렬을 위해 캐시를 무시하는 알고리즘에 사용되는 이 접근 방식의 작업 및 캐시 복잡성에 대해 설명합니다. 다방향 병합의 작업 복잡도는 이진 병합 정렬과 동일하지만 캐시 복잡도는 토너먼트 트리를 채우고 입력 배열에 액세스하는 데 필요한 캐시 미스 수에 의해 결정되며 R이 다음보다 작으면 최적화할 수 있습니다. 작은 상수 C에 대한 C*M/B
01:15:00 이 섹션에서 발표자는 다중 병합 정렬 알고리즘의 캐시 복잡성에 대해 논의하고 이를 이진 병합 정렬 알고리즘과 비교합니다. 다중 병합 정렬 알고리즘은 문제를 크기 n/R의 하위 문제로 나누고 이를 병합하기 위해 n/B 캐시 미스를 지불하는 것을 포함합니다. 재귀 트리의 수준 수는 n/cm의 로그 밑수 R이고 리프 크기는 cm입니다. 화자는 R을 M/B의 세타와 동일하게 설정하여 최대한 크게 하고 캐시 복잡도를 분석한 결과 세타 n log n을 B log M으로 나눈 값임이 밝혀졌습니다. 이진 병합 정렬 알고리즘과 비교하여 멀티 -way 병합 정렬 알고리즘은 캐시 미스에서 로그 M의 계수를 저장합니다. 그러나 알고리즘은 캐시를 무시하지 않으며 특정 시스템에 대해 R 값을 조정해야 합니다. 이는 캐시를 놓고 경쟁하는 다른 작업이 실행 중인 경우 문제가 될 수 있습니다.
01:20:00 이 섹션에서 발표자는 K개의 제곱 요소와 K개의 정렬된 목록을 병합할 수 있는 캐시 무시 정렬 알고리즘인 깔때기형 정렬 알고리즘에 대해 설명합니다. 이 병합의 비용은 다방향 병합 정렬 알고리즘과 동일한 것으로 표시되지만 깔때기 정렬 알고리즘은 캐시를 인식하지 못하며 범위가 최적입니다. 발표자는 K 깔때기의 모양에 대한 그림을 제시하고 알고리즘이 요소를 버퍼에 공급하는 K 깔때기의 제곱근으로 재귀적으로 구성되며, 버퍼는 다시 K 깔때기의 최종 출력 제곱근에 요소를 공급하여 다음을 생성한다고 설명합니다. K 깔때기의 출력. 발표자는 또한 b-트리, 순서가 지정된 파일 유지 관리 및 우선 순위 대기열과 같은 다른 많은 캐시 무시 알고리즘 및 데이터 구조가 있다고 언급하고 시청자가 온라인에서 이에 대해 자세히 알아보도록 초대합니다.
이 비디오는 결정론적 및 비결정론적 병렬 프로그래밍과 관련된 다양한 개념에 대해 설명합니다. 연사는 비정상적인 동작과 어려운 디버깅으로 이어질 수 있으므로 비결정론을 피하는 것의 중요성을 강조합니다. 비결정성을 관리하기 위한 전략에는 고정 값 사용, 레코드 재생, 분석 도구, 캡슐화 및 단위 테스트가 포함됩니다. 회전 대 양보, 재진입 대 비재진입, 공정 대 불공평을 포함하여 뮤텍스의 사용을 자세히 살펴봅니다. 연사는 또한 병렬 프로그래밍의 맥락에서 맥락 전환의 개념과 "스키 대여 문제"에 대해서도 언급합니다. 이 세그먼트는 멀티 코어 프로세서에서 성능 엔지니어링의 기본 원칙을 논의하면서 끝납니다.
비디오의 두 번째 부분에서는 병렬 프로그래밍의 교착 상태 문제를 다루고 대기 주기가 없도록 보장하는 뮤텍스의 선형 순서 지정과 같이 교착 상태를 방지하는 솔루션을 제공합니다. 또한 발표자는 중요한 영역을 모든 업데이트를 한 번에 커밋하는 트랜잭션으로 표현하여 원자성을 보장하는 트랜잭션 메모리의 개념을 소개합니다. 그런 다음 비디오는 유한 소유권 배열과 함께 잠금 기반 접근 방식을 사용하는 알고리즘과 글로벌 잠금 없이 교착 상태 및 기아 상태를 방지하기 위한 릴리스 정렬 필요 메서드를 제시합니다. 마지막으로 알고리즘 릴리스 정렬 및 재취득에 대해 설명합니다. 이는 여러 잠금이 동시에 잠금을 획득하려고 시도하지 않도록 하여 성능 문제를 방지합니다.
00:00:00 이 섹션에서 강사는 프로그래밍의 결정론 개념과 병렬 컴퓨팅과의 관계를 소개합니다. 모든 메모리 위치가 모든 실행에서 동일한 값 시퀀스로 업데이트되고 프로그램이 항상 동일하게 동작하는 경우 프로그램은 결정론적입니다. 결정론적 프로그램은 반복 가능하다는 장점이 있어 디버그하기가 더 쉽습니다. 강사는 디버그하기 어려운 비정상적인 동작을 나타낼 수 있는 비결정적 병렬 프로그램을 절대 작성하지 않는 것이 중요하다고 강조합니다. 그러나 실제로는 병렬 컴퓨팅에서 비결정성을 피하는 것이 어려울 수 있습니다.
00:05:00 이 섹션에서 발표자는 비결정론적 병렬 프로그래밍과 이것이 때때로 더 나은 성능으로 이어질 수 있지만 필요한 경우가 아니면 피해야 한다는 사실에 대해 논의합니다. 발표자는 프로그램을 그런 식으로 작성해야 하는 경우 비결정성을 관리하기 위한 테스트 전략을 고안할 것을 권장합니다. 전략의 예로는 비결정론 해제, 난수에 동일한 시드 사용 또는 임의로 변경될 수 있는 프로그램 입력에 고정 값 제공 등이 있습니다. 발표자는 비결정론으로 인한 프로그램의 버그를 처리하는 방법의 중요성을 강조합니다.
00:10:00 이 섹션에서 발표자는 레코드 재생, 비결정론 캡슐화, 결정론적 대안 대체, 분석 도구 사용 및 단위 테스트와 같은 비결정론적 프로그래밍을 처리하기 위한 전략에 대해 이야기합니다. 발표자는 코드에서 버그를 잡을 가능성을 높이기 위해 비결정성을 제어하는 것의 중요성을 강조합니다. 발표자는 또한 비결정적 프로그래밍을 처리하는 방법을 설명하기 위해 해시 테이블에서 상호 배제 및 원자성을 사용하는 예를 제공합니다.
00:15:00 이 섹션에서 발표자는 동일한 위치에 액세스하는 병렬 명령이 레이스 버그를 유발하고 시스템의 무결성을 파괴할 수 있는 방법에 대해 설명합니다. 표준 솔루션은 일부 명령을 원자적으로 만드는 것입니다. 즉, 시스템의 나머지 부분에서 완전히 실행되거나 전혀 실행되지 않는 것으로 표시됩니다. 이를 위해 잠금 및 잠금 해제 멤버 기능을 가진 객체인 상호 배제 잠금 또는 뮤텍스 잠금이 사용됩니다. 각 슬롯은 뮤텍스 잠금 및 슬롯 컨텍스트에 대한 포인터 헤드가 있는 구조체로 만들어져 목록에 액세스하기 전에 잠금 및 잠금 해제 기능을 사용할 수 있으므로 시스템의 정확성이 보장됩니다.
00:20:00 이 섹션에서 비디오는 뮤텍스를 사용하여 원자성을 구현하는 방법과 이것이 결정 경쟁과 어떻게 관련되는지 살펴봅니다. 뮤텍스 잠금은 중요한 섹션이 원자적임을 보장할 수 있지만 결과 코드는 경우에 따라 원하는 것일 수 있는 결정 경쟁으로 인해 비결정적입니다. 이 비디오는 데이터 경쟁과 결정 경쟁 간의 차이점을 이해하는 것의 중요성을 강조하고 단순히 데이터 경쟁을 제거한다고 해서 반드시 코드에 버그가 없다는 것을 의미하지는 않는다는 점에 주목합니다. 코드에서 잘못된 긍정 또는 누락된 레이스 버그를 방지하기 위해 비결정론을 감지하는 방법을 갖는 것이 중요합니다.
00:25:00 이 섹션에서 발표자는 데이터 경합이 없다고 해서 반드시 코드에 버그가 없다는 것을 의미하지는 않는다고 설명합니다. 데이터 경합은 코드의 긍정적인 측면이 아니지만, 원자성을 제공하기 위해 잠그는 예는 원자성 위반으로 이어질 수 있습니다. 또한 두 개의 병렬 프로세스가 동일한 값에 액세스하는 경우와 같이 양성 경합이 발생할 수 있으며, 이는 동일한 결과를 초래할 수 있지만 일부 아키텍처에서는 잘못된 값으로 이어질 수도 있습니다. 화자는 어떤 사람들은 온건한 인종을 무해하다고 생각하지만, 여전히 그들을 식별하고 피하는 것이 필수적이라고 주장합니다.
00:30:00 이 섹션에서 발표자는 특히 여러 프로세스가 동일한 위치에 값을 설정하려고 할 때 발생할 수 있는 경쟁 조건으로 인해 비결정적 프로그래밍의 위험에 대해 설명합니다. 연사는 의도적인 레이스를 허용하지만 올바르게 사용하지 않으면 위험할 수 있는 "실크"의 개념을 소개합니다. 레이스의 복잡성으로 인해 디버깅이 어려워지고 올바른 코드를 감지하는 데 도움이 되는 도구가 혼동될 수 있습니다. 연사는 또한 뮤텍스와 그 매개변수의 구현이 항복 또는 회전 여부와 같은 동작에 어떻게 영향을 미칠 수 있는지에 대해 논의합니다.
00:35:00 이 섹션에서 비디오는 병렬 프로그래밍에서 뮤텍스의 세 가지 기본 속성인 회전 대 양보, 재진입 대 비재진입, 공정 대 불공정에 대해 설명합니다. 회전 대 양보의 개념은 스레드가 유휴 상태로 있지 않고 잠금에 대한 액세스를 지속적으로 확인하는 대신 보다 효율적인 실행을 위해 운영 체제에 제어권을 양보한다는 개념입니다. 재진입 뮤텍스는 이미 잠금을 보유하고 있는 스레드가 잠금을 다시 획득하도록 허용하는 반면 비재진입 잠금은 스레드가 이미 가지고 있는 뮤텍스를 다시 획득하려고 시도하면 교착 상태가 됩니다. 마지막으로 공정한 뮤텍스는 기아 문제의 가능성을 방지하기 위해 가장 오래 대기한 스레드가 먼저 잠금을 얻도록 합니다. 비디오는 또한 어셈블리 언어로 간단한 회전 뮤텍스 구현을 제공합니다.
00:40:00 이 섹션에서 비디오는 병렬 프로그래밍에서 뮤텍스를 사용하는 방법과 뮤텍스를 가져오는 대신 교환 명령을 사용하는 이유에 대해 설명합니다. 교환 작업은 권리와 유사하며 권리를 행사하기 위해서는 해당 현금 라인을 다른 현금 라인에서 무효화하고 수정 또는 배타적 상태로 보유해야 한다고 설명합니다. 이로 인해 메모리 네트워크에 트래픽이 생성되고 프로세스 속도가 느려집니다. 반면에 교환 명령을 사용하면 캐시 라인이 공유 상태가 되므로 프로세스 속도가 빨라지고 트래픽이 적게 생성됩니다.
00:45:00 이 섹션에서 화자는 회전하는 뮤텍스와 양보하는 뮤텍스의 차이점에 대해 설명합니다. 회전하는 뮤텍스에서 프로그램은 뮤텍스가 잠금 해제되었는지 계속 확인하는 반면 양보하는 뮤텍스에서는 프로그램이 운영 체제에 제어권을 양보하여 다른 일정을 잡을 수 있도록 합니다. 발표자는 회전하는 뮤텍스와 양보하는 뮤텍스의 두 가지 목표를 모두 달성하는 경쟁 뮤텍스라고 하는 또 다른 종류의 뮤텍스가 있다고 언급합니다. 발표자는 또한 대기 중인 스레드에 알리기 위해 메시지 전달 또는 인터럽트를 사용하는 방법을 탐색하지만 더 간단한 솔루션은 상호 배제 메커니즘을 사용하는 것이라고 언급합니다.
00:50:00 이 섹션에서 발표자는 운영 체제가 사용 가능한 프로세서의 스레드 간에 전환하는 빈도인 컨텍스트 전환의 개념을 설명합니다. 일반적으로 시스템은 초당 약 100회 컨텍스트 전환을 수행합니다. 즉, 각 전환에는 약 10밀리초가 걸립니다. 그러나 이것은 간단한 명령어의 실행 시간보다 훨씬 더 긴 시간입니다. 즉, 스레드가 다시 들어와서 잠금을 잡을 기회를 갖기 전에 실행할 수 있는 많은 명령어가 있음을 의미합니다. 이 문제는 스피닝과 항복을 조합하여 해결할 수 있습니다. 화자는 이론 문헌에서 이것을 "스키 대여 문제"라고 부릅니다.
00:55:00 이 섹션에서는 스포츠 장비 구매 또는 대여의 예를 사용하여 특정 작업을 위한 장비 구매 또는 대여 여부를 결정하는 과정에 대해 설명합니다. 화자는 시청자들에게 렌탈 비용과 구매 비용을 고려하도록 유도하고 비용이 구매 비용과 같을 때까지 렌탈한 다음 구매를 제안합니다. 또한 이 비디오는 컨텍스트 전환 시간, 디스크 액세스 시간의 개념 및 한 번에 여러 잠금을 보유할 때 교착 상태 문제를 탐구합니다. 전반적으로 이 세그먼트는 멀티 코어 프로세서의 성능 엔지니어링 기본 원칙을 다룹니다.
01:00:00 이 섹션에서 발표자는 교착 상태에 대해 설명합니다. 교착 상태는 두 스레드가 다른 스레드에 필요한 리소스를 보유하고 있어 성능이 저하되는 현상입니다. 교착 상태에는 세 가지 기본 조건이 있습니다. 상호 배제(자원에 대한 배타적 제어), 비선점(종료될 때까지 자원 보유) 및 순환 대기(다음 스레드가 보유한 자원을 기다리는 스레드 주기)입니다. 이러한 제약 조건 중 하나를 제거하면 교착 상태 문제를 해결할 수 있습니다. 화자는 교착 상태의 문제를 설명하기 위해 Edsger Dijkstra의 시험 문제를 기반으로 Tony Hoare가 말한 "Dining Philosophers"를 사용합니다. 이 이야기는 테이블에 둘러앉은 철학자들이 젓가락으로 국수를 먹는데 각 국수 접시는 두 개의 젓가락 사이에 위치하며 국수를 먹기 위해서는 두 개의 젓가락이 필요합니다. 철학자들은 국수를 먹기 위해 좌우에 있는 젓가락을 잡습니다. 하지만 모두 왼쪽에 있는 왼쪽 젓가락을 집으면 결국 굶어 죽게 됩니다.
01:05:00 이 섹션에서 발표자는 병렬 프로그래밍의 교착 상태 문제에 대해 논의하고 교착 상태를 피하면서 비선점을 보장하는 솔루션인 뮤텍스의 선형 순서 지정을 제공합니다. 각 뮤텍스에 번호를 매기고 숫자 순서에 따라 전략적으로 잠그면 프로그래머는 대기 주기(교착 상태의 필수 조건)가 발생하지 않도록 보장할 수 있습니다. 그러나 그는 이러한 잠금을 통해 추가 비결정론을 도입하면 문제가 발생할 수 있으므로 프로그래머가 실크에서 런타임 시스템의 잠금 캡슐화를 인식하도록 주의를 줍니다. 그는 병렬 프로그램을 설계할 때 신중한 고려의 중요성을 강조하면서 단 하나의 잠금으로 교착 상태가 발생할 수 있는 예를 공유합니다.
01:10:00 이 섹션에서 발표자는 잠금을 지정할 필요 없이 원자성이 암묵적으로 발생하는 데이터베이스 트랜잭션을 포함하는 최근 연구 수준 기술인 트랜잭션 메모리의 주제에 대해 자세히 설명합니다. 연사는 트랜잭션 메모리가 동시 그래프 계산, 즉 가우시안 제거에서 어떻게 유용한지에 대한 예를 제공합니다. 여기서 두 개의 노드가 동시에 제거되면 원자성 위반이 발생합니다. 트랜잭션 메모리의 이면에 있는 아이디어는 임계 영역을 트랜잭션으로 나타내고 커밋 시 임계 영역의 모든 메모리 업데이트가 마치 한 번에 발생한 것처럼 나타납니다.
01:15:00 이 섹션에서 발표자는 트랜잭션 메모리의 충돌 해결, 경합 해결, 전달 진행 및 처리량에 대해 논의합니다. 그들은 유한 소유권 배열과 함께 잠금 기반 접근 방식을 사용하는 알고리즘과 전역 잠금 없이도 교착 상태와 기아 상태를 방지하기 위한 릴리스 정렬 필요 메서드를 도입합니다. 알고리즘은 트랜잭션이 중단될 때 롤백 또는 원자적 커밋을 허용하기 위해 읽기 및 쓰기를 기록합니다. 잠금 배열은 해시 함수가 매핑되는 위치를 잠그는 데 사용되어 잠금을 공정하게 획득할 수 있습니다. 이 알고리즘은 성능을 희생하거나 교착 상태를 일으키지 않고 동시 트랜잭션을 허용합니다.
01:20:00 이 섹션에서 발표자는 릴리스 정렬 및 재획득이라는 알고리즘에 대해 설명합니다. 이 알고리즘은 탐욕스럽게 메모리 위치의 잠금을 획득하려고 시도하는 방식으로 작동하며 충돌이 발생하면 트랜잭션이 보유한 잠금을 해제하지 않고 롤백합니다. 그런 다음 알고리즘은 액세스하려는 위치의 인덱스보다 큰 인덱스를 가진 모든 잠금을 해제합니다. 그런 다음 원하는 잠금을 획득하고 최종적으로 해제된 잠금을 정렬된 순서로 획득합니다. 이 프로세스는 트랜잭션이 성공할 때까지 반복됩니다. 이 알고리즘은 성능 문제를 일으킬 수 있는 여러 잠금이 동시에 잠금을 획득하려고 시도하는 것을 방지하도록 설계되었습니다.
Charles Leiserson은 YouTube 동영상에서 잠금 없는 동기화의 개념을 탐구합니다. 그는 순차 실행을 보장하기 위해 명령의 전역 선형 순서의 필요성을 보여주는 예를 제공하고 잠금 사용의 어려움과 잠재적인 문제를 피하면서 순차 일관성을 통해 상호 배제를 달성할 수 있는 방법에 대해 설명합니다. Leiserson은 Peterson의 알고리즘을 로드 및 저장 작업만 사용하여 동시 프로세스의 간섭 없이 중요 섹션에 액세스하는 솔루션으로 제시합니다. 비디오는 또한 하드웨어 재정렬로 인한 메모리를 통한 동기화 문제와 다른 명령과의 상대적인 순서를 유지하기 위한 메모리 펜스의 개념을 다룹니다. Leiserson은 병렬 시스템에 대한 순차적 일관성을 지원하는 것이 유익하지만 하드웨어 설계자에게는 달성하기 어렵다고 주장합니다.
비디오의 두 번째 부분에서는 병렬 프로그램의 오류를 방지하기 위한 메모리 펜스와 동기화 명령의 사용에 대해 설명합니다. 발표자는 메모리 펜스를 암시적으로 또는 명시적으로 구현하는 다양한 방법과 프로세서의 다양한 측면에서 작업하는 여러 팀 간의 신중한 엔지니어링 및 조정의 중요성을 탐구합니다. 또한 강사는 C11 언어 표준에서 잠금 해제 알고리즘의 일부로 CAS 명령어를 사용하여 상수 공간만 사용하여 n-스레드 교착 상태가 없는 상호 배제 알고리즘의 뮤텍스를 구현하는 방법에 대해 설명합니다. Charles Leiserson은 다중 스레드 시스템에서 잠금을 사용하는 문제와 대신 CAS를 사용하는 솔루션에 대해 설명합니다. 잠금을 오랫동안 유지하는 스레드는 동일한 리소스에 액세스하기 위해 대기 중인 다른 스레드를 잠재적으로 차단할 수 있기 때문입니다. 또한 비디오는 비교 및 교환과 관련된 ABA 문제의 잠재적인 문제를 강조하고 주제에 관심이 있는 사람들이 잠금 해제 알고리즘에 대해 자세히 알아보도록 권장합니다.
00:00:00 및 해당 지침은 인터리브되어 모든 지침의 전역 선형 순서를 생성합니다. 이것은 이론적 관점에서 가장 중요한 메모리 모델인 순차적 일관성의 메모리 모델 이면에 있는 아이디어입니다. 잠금이 없는 경우 병렬 프로그램의 동작이 메모리 모델에 따라 달라지기 때문에 메모리 모델을 이해하는 것이 중요합니다. 강의에서 제시된 한 가지 예는 사용 중인 메모리 모델에 따라 두 개의 프로세서가 코드를 병렬로 실행한 후 둘 다 0의 값을 가질 수 있는지 질문하여 이 점을 설명합니다.
00:05:00 이 섹션에서 Charles Leiserson은 로드와 스토어가 순차적으로 실행되기 위해 전역 선형 순서를 준수하는 것처럼 보여야 하는 잠금 없는 동기화의 개념에 대해 설명합니다. 그는 다양한 값을 인터리빙하는 예를 사용하여 발생할 수 있는 다양한 실행 경로와 하드웨어가 원하는 대로 수행할 수 있는 방법을 보여줍니다. 그는 또한 값을 인터리브하는 여러 가지 방법이 있을 수 있지만 실행이 일관되려면 로드 및 저장이 선형 순서를 따르는 것처럼 보여야 한다고 설명합니다. 궁극적으로 Leiserson은 두 값이 모두 0으로 끝나는 실행은 없다고 결론을 내립니다. 흥미로운 점은 현대 컴퓨터에서 어느 것도 순차적 일관성을 제공하지 않는다는 것입니다.
00:10:00 이 섹션에서는 순차적 일관성의 개념에 대해 설명합니다. 여기에는 명령과 순서 간의 관계, 오른쪽 화살표 연결, 프로세서 순서 및 명령 시퀀싱 간의 선형 관계에 대한 이해가 포함됩니다. 또한 순차적 일관성을 고려하고 로드 및 저장을 사용하여 공유 데이터 구조를 구현함으로써 강력한 명령이나 잠금을 사용하지 않고 상호 배제를 수행할 수 있습니다. 강의 노트는 테스트 및 설정 또는 비교 및 교환과 같은 특수 작업을 사용하는 방법을 설명하지만 제시된 솔루션은 잠금을 사용할 때 발생하는 교착 상태 또는 기타 나쁜 일을 방지합니다.
00:15:00 이 섹션에서 Charles Leiserson은 로드 및 저장 작업만 사용하여 동시 프로그램에서 상호 배제를 달성하기 위한 Peterson의 알고리즘을 설명합니다. 이 알고리즘을 사용하면 두 개의 동시 프로세스인 Alice와 Bob이 일련의 변수와 턴테이킹 메커니즘을 사용하여 서로 간섭하지 않고 코드를 실행할 수 있습니다. 이 코드는 한 번에 하나의 프로세스만 중요한 섹션에 들어가 공유 리소스를 수정할 수 있도록 합니다. 잠금과 달리 Peterson의 알고리즘은 잠금 획득 또는 해제에 의존하지 않고 대신 로드 및 저장을 사용하여 상호 배제를 달성합니다.
00:20:00 이 섹션에서 발표자는 잠금을 사용하지 않고 중요 섹션에서 상호 배제를 달성하기 위한 Peterson의 알고리즘에 대해 설명합니다. 그는 한 번에 한 사람만 크리티컬 섹션에 들어갈 수 있으며, 알고리즘은 크리티컬 섹션에 들어가고 싶은 사람만 가고 싶어하는 사람이라면 그렇게 할 수 있도록 보장한다고 설명합니다. 그런 다음 발표자는 알고리즘의 증명을 제시합니다. 여기에는 Alice와 Bob이 함께 임계 영역에 있다고 가정하고 모순을 도출하는 것이 포함됩니다. 증명은 "이전에 발생" 관계와 실행된 명령의 프로그램 순서에 의존합니다.
00:25:00 이 섹션에서는 화자가 잠금 없이 동기화하는 과정을 설명합니다. 명령 체인을 설정하고 동기화 오류를 피하기 위해 올바른 순서로 발생하는지 확인합니다. 그들은 데모로 공유 리소스에 액세스하려는 Bob과 Alice의 예를 사용합니다. 그들은 동기화할 때 엔지니어가 주의를 기울이고 올바른 순서로 발생하는지 확인하기 위해 "일보다 먼저 발생"을 검토해야 한다고 설명합니다.
00:30:00 이 섹션에서 Charles Leiserson은 모델 검사의 개념과 네트워크, 보안 및 캐시 프로토콜 분석에서의 모델 사용에 대해 설명합니다. 그런 다음 기아 상태의 자유를 보장하지만 두 개 이상의 프로세스에서 작동하지 않는 Peterson 알고리즘의 속성을 설명합니다. Leiserson은 또한 메모리를 통한 동기화 문제와 최신 프로세서의 순차적 일관성 부족으로 인해 메모리 일관성이 완화되고 동기화를 올바르게 수행하는 데 어려움이 있음을 탐구합니다.
00:35:00 로드 대기 시간 문제를 일으키지 않고 지침을 재정렬하는 것이 안전합니까? 두 번째 제약 조건은 명령어 간에 데이터 종속성이 없는 경우입니다. 즉, 명령어가 데이터를 공유하지 않거나 메모리에서 동일한 위치를 사용하지 않습니다. 이 경우 명령을 재정렬하면 로드를 더 일찍 수행할 수 있고 결과를 기다리는 동안 다른 작업을 수행할 수 있으므로 성능을 개선하고 오버로드 대기 시간을 처리할 수 있습니다. 이러한 하드웨어 수준 개념을 이해하면 소프트웨어에 대한 추론과 성능 최적화에 도움이 될 수 있습니다.
00:40:00 이 섹션에서 Charles Leiserson은 잠금 없이 동기화된 재정렬의 개념을 설명합니다. 그는 특히 프로세서가 작동 중이거나 명령 스트림에 거품이 있을 때 동시성이 없는 한 재정렬을 수행하는 것이 안전하다고 설명합니다. 최신 프로세서에서 하드웨어는 버퍼에 데이터를 저장하고 메모리 시스템으로 직접 이동하여 부하를 우회하기 때문입니다. 그러나 이러한 우회는 저장소 중 하나가 로드되는 항목인 경우 정확성 문제로 이어질 수 있습니다.
00:45:00 이 섹션에서 Charles Leiserson은 하드웨어 재정렬이 발생하는 방식과 순차 일관성을 충족하지 못하는 이유, 그리고 x86에 순차 일관성보다 약한 총 저장 순서라는 메모리 일관성 모델이 있는 이유를 설명합니다. 전체 매장 주문에 대한 규칙에는 로드와 함께 로드를 재정렬하지 않는 것, 로드가 외부 프로세서에 의해 동일한 순서로 표시되는 것, 매장이 매장과 함께 재정렬되지 않음, 로드가 이전 매장과 함께 다른 위치로 재정렬될 뿐 이전 로드가 로드되지 않는 것이 포함됩니다. 같은 위치. 잠금 명령과 메모리 순서는 전체 순서를 따릅니다.
00:50:00 이 섹션에서 발표자는 명령어 재정렬이 순차적 일관성을 위반하고 잘못된 값을 초래할 수 있는 방법에 대해 설명합니다. 재정렬은 하드웨어와 컴파일러 모두에서 발생할 수 있으며 잠금 명령어는 다른 명령어보다 먼저 이동하지 않는다는 것을 아는 것이 중요합니다. 스피커는 또한 로드가 다른 주소에 있는 경우 로드가 상점보다 먼저 갈 수 있음을 언급합니다. 재정렬의 위험은 특정 재정렬이 발생하면 완전히 망가질 수 있는 Peterson의 알고리즘에서 입증됩니다. 따라서 메모리를 통해 동기화할 때 이러한 문제를 방지하기 위해 결정적 코드를 작성하는 것이 중요합니다.
00:55:00 이 섹션에서 Charles Leiserson은 저장 전에 발생하는 특정 로드를 피하는 것이 중요한 병렬 및 동시 코드를 작성할 때 재정렬 문제에 대해 설명합니다. 이러한 시나리오를 처리하기 위해 엔지니어는 다른 명령과의 상대적인 순서를 유지하는 메모리 펜스를 도입하지만 복잡성이 증가하고 잠재적인 버그가 발생합니다. Leiserson은 또한 병렬 시스템이 순차 일관성을 지원하는 것이 유익하지만 하드웨어 설계자가 달성하기 어려운 과제라고 주장합니다.
01:00:00 이 섹션에서 발표자는 병렬 프로그램에서 오류가 발생하지 않도록 방지하는 메모리 펜스와 동기화 명령의 중요성에 대해 설명합니다. 발표자는 명시적으로 명령으로 또는 잠금 및 교환과 같은 다른 동기화 명령을 통해 암시적으로 메모리 펜스를 구현할 수 있는 다양한 방법을 설명합니다. 그러나 메모리 펜스가 실제로 프로그램 속도를 늦출 수 있는 경우가 있어 프로세서의 서로 다른 측면에서 작업하는 서로 다른 팀 간의 신중한 엔지니어링 및 조정의 중요성을 보여줍니다. 또한 스피커는 컴파일러가 변수를 최적화하지 않고 병렬 코드에서 오류가 발생하지 않도록 휘발성 변수 및 컴파일러 펜스를 사용하도록 조언합니다.
01:05:00 이 섹션에서 강사는 C11 언어 표준에서 잠금 없는 동기화에 대해 설명합니다. 이 표준은 교착 상태가 없는 상호 배제 알고리즘을 위해 메모리 펜스 또는 원자 비교 및 교환과 같은 값비싼 작업을 사용해야 하는 원자로 선언할 수 있는 약한 메모리 모델을 정의합니다. 여기에서 잠금 해제 알고리즘의 일부로 CAS 명령(비교 및 스왑)을 살펴봅니다. 명령은 메모리의 값이 새 값으로 교환하기 전에 이전 값과 동일한지 확인합니다. 모두 원자적으로 수행됩니다. CAS를 사용하면 일정한 공간만 사용하여 n-스레드 교착 상태가 없는 상호 배제 알고리즘의 뮤텍스를 구현할 수 있습니다. true 값을 얻을 때까지 회전하는 잠금 명령은 누군가가 잠금을 보유하고 있음을 나타내는 true로 교체하는 데 사용됩니다.
01:10:00 이 섹션에서는 Charles Leiserson 교수가 CAS(비교 및 교환)를 사용하여 동기화 문제를 해결하는 방법을 설명합니다. 그는 CAS를 잠금 장치로 사용하는 방법을 시연하고 학생이 제시한 코드의 버그를 수정합니다. 그런 다음 그는 배열의 값 합계를 계산하는 데 사용되는 잘못된 코드를 제시하여 경합 상태로 이어집니다. 그는 일반적인 솔루션으로 뮤텍스 잠금을 소개하고 잠금을 획득한 후 스레드가 교체되어 다른 스레드가 잠금을 기다리게 하여 진행을 방해하는 잠재적인 문제를 설명합니다.
01:15:00 이 섹션에서 Charles Leiserson은 다중 스레드 시스템에서 잠금을 사용하는 문제와 대신 CAS를 사용하는 솔루션을 설명합니다. 잠금을 사용하면 스레드가 잠재적으로 오랫동안 잠금을 유지하여 동일한 리소스에 액세스하기 위해 대기 중인 다른 스레드를 차단할 수 있습니다. 그러나 CAS를 사용하면 임시 계산 후 x를 로드한 다음 이전 결과를 저장하고 임시 결과를 해당 이전 값에 추가하여 새로운 값을 생성할 수 있는 변수 old 및 new를 갖는 동시에 임시를 계산한 후 x를 저장합니다. 이전 값이 변경되지 않은 경우 교체됩니다. Charles는 또한 비교 및 교환과 관련된 ABA 문제를 언급하고 주제에 관심이 있는 사람들이 잠금 해제 알고리즘에 대해 자세히 알아보도록 권장합니다.
이 비디오에서 MIT EECS 부서의 Saman Amarasignhe 교수는 성능 엔지니어링에서 DSL(도메인별 언어) 사용 및 자동 튜닝의 이점에 대해 설명합니다. 그는 범용 언어로 설명하기 어려운 영역별 도메인을 캡처하여 프로그래머가 더 나은 성능을 위해 도메인 전문가의 지식을 활용할 수 있도록 하는 DSL의 중요성을 강조합니다. Singh은 그래프 파티셔닝 및 계산에서 그래프 모양의 중요성을 포함하여 DSL을 사용한 그래프 프로세스의 최적화에 대해 논의합니다. 그는 이미지 처리를 위한 DSL Halide를 소개합니다. 이는 빠른 코드 최적화와 시스템 간 이식성을 가능하게 합니다. 그는 Google 및 Adobe와 같은 다양한 산업에서 Halide의 사용에 대해 논의합니다. 궁극적으로 그는 병렬성, 지역성 및 중복 작업에 초점을 맞추면서 코드를 최적화하는 다양한 접근 방식을 실험하는 것의 중요성을 강조합니다.
비디오는 또한 성능 엔지니어링의 문제와 프로그램이 효율적으로 실행되기 위한 최적의 매개변수를 찾는 문제에 대해 설명합니다. 발표자는 자동 튜닝이 최적의 값을 찾기 위해 큰 매개변수 공간을 자동으로 검색하여 이 문제를 해결할 수 있다고 제안합니다. 그는 철저한 검색이 비실용적일 수 있으며 휴리스틱 기반 솔루션이 최적이 아닐 수 있다고 지적합니다. 허용 가능한 값의 공간을 정의하고 성능 결과를 기반으로 반복하는 자동 튜닝은 최적의 솔루션을 찾는 프로세스를 가속화할 수 있습니다. 연사는 또한 전체 검색보다 더 효율적이고 효과적으로 일정을 생성할 수 있는 Try의 일정 생성에 자동 튜닝을 적용하는 방법에 대해 설명합니다.
00:00:00 이 섹션에서는 MIT EECS 부서의 교수인 Saman Amarasignhe 교수가 도메인별 언어 및 자동 튜닝에 대해 이야기합니다. 그는 이러한 언어가 범용 언어로 설명하기 어려운 특정 영역별 도메인을 캡처하기 때문에 엔지니어링 이점이 있다고 설명합니다. 도메인 특정 언어는 이해하고 유지하기가 훨씬 쉽고 프로그래머가 도메인 전문가의 지식을 활용하여 정말 좋은 성능을 얻을 수 있습니다. 또한 올바르게 빌드된 경우 도메인별 언어는 하위 수준 결정을 컴파일러에 맡기므로 최적화 프로세스가 훨씬 간단해집니다.
00:05:00 이 섹션에서 발표자는 성능 엔지니어링에서 도메인별 언어(DSL) 사용에 대해 논의합니다. 가능할 때마다 성능을 컴파일러에 맡기도록 권장하고 그래프 처리를 위한 세 가지 프로그래밍 언어/프레임워크인 Graffiti, Halide 및 OpenTuner를 도입합니다. 그들은 그래프가 Google 검색에서 추천 엔진에 이르기까지 어디에나 있다고 지적하고 Google에서 웹 페이지 순위를 매기는 데 사용하는 PageRank 알고리즘을 더 깊이 탐구합니다. PageRank 알고리즘은 웹 페이지의 이웃을 살펴보고 그들의 영향에 따라 새로운 순위를 계산하여 성능 공학에서 그래프 처리의 중요성을 보여줍니다.
00:10:00 이 섹션에서 발표자는 막대한 양의 데이터를 처리하고 전체 그래프에 대한 계산을 반복하는 것과 관련된 그래프 알고리즘에 대해 논의합니다. 성능을 위해 코드를 최적화하기 위해 DSL을 사용할 수 있습니다. 그래프 처리에 사용되는 알고리즘 유형에는 전체 그래프가 계산에 참여하는 토폴로지 기반 알고리즘과 그래프의 작은 영역 또는 일부에서 처리가 수행되는 데이터 기반 알고리즘이 포함됩니다. 또한 그래프 반전을 수행하는 방법에는 여러 가지가 있으며 각 방법에는 서로 다른 결과 집합이 있습니다.
00:15:00 이 섹션에서는 큰 그래프를 더 작은 조각으로 나누는 그래프 분할 주제에 대해 설명합니다. 그래프 분할의 장점은 병렬 처리가 가능하다는 점과 작업 중인 노드가 캐시에 들어갈 만큼 충분히 작다는 의미인 좋은 지역성을 제공한다는 것입니다. 그래프 파티셔닝은 소셜 네트워크 그래프에도 멱함수 관계가 있기 때문에 영향을 미칩니다. 즉, 특정 노드는 다른 노드보다 더 많은 연결 또는 더 큰 영향을 미치며 이러한 그래프를 처리할 때 특정 연결 및 노드는 그 중요성에 따라 더 많은 주의를 기울여야 합니다.
00:20:00 이 섹션에서 발표자는 계산에서 그래프 모양의 중요성, 특히 그래프의 크기와 지역성이 병렬 알고리즘의 효율성에 어떤 영향을 미칠 수 있는지에 대해 논의합니다. 주어진 알고리즘에 대해 최상의 성능을 달성하기 위해 필요한 병렬성, 지역성 및 추가 작업과 같은 요소가 신중하게 균형을 이루어야 하며 그래프 유형, 알고리즘 유형 및 사용 중인 하드웨어에 따라 올바른 방법을 선택해야 합니다. 이러한 요소를 더 잘 최적화하기 위해 처리 방법에서 상수 알고리즘을 분리하기 위해 도메인별 언어가 개발되었습니다.
00:25:00 이 섹션에서 연사는 DSL(도메인 특정 언어)을 사용하여 더 높은 수준에서 코드를 작성하여 더 간단하고 우아하게 만드는 방법에 대해 설명합니다. 다양한 알고리즘의 예와 DSL이 이를 계산하는 간단한 방법을 제공하는 방법을 제공합니다. 또한 연사는 병렬 처리를 허용하면서 가능한 최상의 속도를 얻기 위해 DSL 스케줄링을 최적화하는 방법을 설명합니다. 코드는 그래프나 기계의 변화에 따라 달라질 수 있지만 알고리즘은 동일하게 유지됩니다. 연사는 최적화된 일정을 생성할 수 있을 만큼 강력하면서도 프로그래밍의 단순성을 제공하는 DSL의 중요성을 강조합니다.
00:30:00 이 섹션에서 발표자는 조밀한 규칙 구조를 가진 이미지 처리에 중점을 둔 또 다른 도메인별 언어인 Halide에 대해 설명합니다. Halide는 최적화된 성능을 달성하는 데 필요한 프로그래밍 양을 줄이는 데 도움이 되며 다른 시스템에서 프로그램의 이식성을 높입니다. 스피커는 Halide가 어떻게 작동하는지 보여주기 위해 3x3 블러 예제를 제공합니다. Halide는 다양한 기술의 다양한 조합을 통해 성능을 최적화한다는 측면에서 앞서 논의한 그래프 언어와 유사한 패턴을 가지고 있습니다.
00:35:00 이 섹션에서 발표자는 DSL(도메인별 언어)의 사용과 코드 성능을 최적화하기 위한 자동 조정에 대해 설명합니다. 그는 유효한 C 코드와 비교하여 Halide라는 DSL을 사용하여 더 빠르게 실행되는 이미지 필터의 예를 제공합니다. Halide를 사용하면 일정에서 알고리즘을 분리할 수 있으므로 실행 중인 순수 기능의 파이프라인을 간단하게 최적화할 수 있습니다. 마지막으로 연사는 사용 가능한 컴퓨팅 리소스에서 최상의 성능을 달성하기 위해 지역성, 병렬성 및 중복 작업 간의 절충이 필요함을 강조합니다.
00:40:00 이 섹션에서 화자는 이미지 처리와 관련하여 지역성의 중요성에 대해 논의합니다. 큰 이미지를 처리할 때 전체 이미지에 작동하는 필터를 한 번에 적용하는 것은 캐시에 맞지 않기 때문에 효율적이지 않습니다. 대신 화자는 이미지를 더 작은 섹션으로 나누고 각 섹션에 필터를 적용하여 지역성과 병렬성에 초점을 맞추도록 제안합니다. 이는 스케줄링 프레임워크를 사용하고 계산 대역폭 및 스토리지 세분성을 최적화하여 달성할 수 있습니다. 더 나은 지역성과 병렬성을 달성하기 위해 일부 중복 작업이 필요할 수도 있습니다.
00:45:00 이 섹션에서 발표자는 Halide 사용에 중점을 둔 도메인 특정 언어 및 자동 조정에 대해 설명합니다. Halide는 라이브러리 기능을 함께 융합할 수 있으며, 이는 더 많은 지역성이 있기 때문에 라이브러리를 호출하는 것보다 빠릅니다. 발표자는 Halide가 양방향 필터 계산 및 분할 알고리즘과 같은 계산 프로세스를 최적화할 수 있는 방법을 보여줍니다. 한 예에서 수동으로 최적화된 라이브러리를 호출하던 MATLAB으로 작성된 분할 알고리즘은 Halide로 작성되었을 때 70배 더 빨랐습니다. Halide는 Google의 중요한 부분이며 Android 휴대 전화에 통합되어 Google Glass에서 사용되었습니다.
00:50:00 이 섹션에서 발표자는 프런트 엔드 처리에 Halide를 사용하는 효과와 다양한 산업에서 어떻게 널리 사용되고 있는지에 대해 논의합니다. Halide는 이전 버전에 비해 4~5%의 속도 증가를 자랑하며, 이는 다운로드한 동영상 수를 고려할 때 Google에 상당한 의미가 있습니다. Adobe는 전체 Photoshop 필터가 Halide로 작성된다고 발표했습니다. Snapdragon 이미지 프로세서와 Intel도 Halide를 사용하기 시작했습니다. 발표자는 또한 성능 엔지니어의 작업을 더 쉽게 만들어주는 최적화 자동화 능력 측면에서 Halide와 Graph가 어떻게 유사점을 공유하는지에 대해서도 논의합니다. 그러나 알고리즘 최적화에 관해서는 특정 컨텍스트 지식이 필요한 상위 수준 변경이므로 자동화하기 어렵습니다. 그럼에도 불구하고 예약된 언어와 같은 도구는 사용자에게 다양한 접근 방식을 시도하고 더 나은 성능을 달성할 수 있는 옵션을 제공합니다.
00:55:00 이 섹션에서 발표자는 최신 컴퓨터 시스템의 복잡성과 코드를 최적화하는 올바른 방법이 없는 방법에 대해 설명합니다. 그들은 다양한 접근 방식을 시도하는 것의 중요성과 캐시, 지역성 및 병렬 처리의 중요성을 강조합니다. 또한 생물학 및 물리학과 같은 다양한 영역의 사람들이 코드 복잡성으로 인해 프로그램을 충분히 빨리 작성할 수 없기 때문에 연구를 추구하기보다 코드를 최적화하는 데 많은 시간을 보내는 방법에 대해서도 논의합니다. 연사는 사람들이 대부분의 시간을 해킹하고 추상화하는 데 보내는 도메인을 찾는 것이 연구를 위해 탐구할 흥미로운 영역이 될 수 있다고 제안합니다. 전반적으로 프로그램을 최적화하기 위해 작업할 공간에는 병렬성, 지역성 및 중복 작업이 포함되며 이 공간에서 재생하는 것은 성능 엔지니어에게 중요합니다.
01:00:00 이 섹션에서 발표자는 프로그램이 최적으로 실행되기 위한 올바른 매개변수를 찾는 것과 관련된 성능 엔지니어링의 과제에 대해 논의합니다. 그는 메모리 할당, 블록 크기 등 조정할 수 있는 매개 변수가 많지만 각 프로그램에 대한 각 매개 변수에 대한 올바른 값을 결정하기 어려울 수 있다고 설명합니다. 그러나 발표자는 최적의 값을 찾기 위해 큰 매개변수 공간을 자동으로 검색함으로써 자동 튜닝이 이 문제를 해결할 수 있다고 제안합니다. 그는 특정 상황에 대한 하드 코딩 규칙을 포함하는 휴리스틱 기반 솔루션이 대부분의 경우 작동할 수 있지만 항상 최적인 것은 아니라고 설명합니다. 연사는 또한 모델이 모든 중요한 요소를 고려하지 않아 최적이 아닌 결과를 초래할 수 있기 때문에 시스템의 구축 모델이 문제가 될 수 있다고 지적합니다.
01:05:00 이 섹션에서 연사는 변화하는 기술이나 진화하는 요구 사항에 직면하여 최적의 솔루션을 찾는 문제에 대해 논의합니다. 그는 프로그래머가 솔루션을 안내하기 위해 사용하는 다양한 "휴리스틱"이 있으며 종종 더 이상 적용할 수 없는 지침이나 경험 법칙을 기반으로 한다고 지적합니다. 한 가지 옵션은 철저한 검색이지만 가능한 순열의 수가 너무 많기 때문에 비실용적일 수 있습니다. 이를 해결하기 위해 연사는 검색 공간을 정리하고 최적의 솔루션을 더 빨리 찾는 방법으로 자동 튜닝을 사용할 것을 권장합니다. 자동 튜닝에는 허용 가능한 값의 공간을 정의하고 테스트할 값을 무작위로 선택한 다음 성능 결과에 따라 반복하는 작업이 포함됩니다. OpenTuner는 이 반복 프로세스의 속도를 높이기 위해 힐 클라이머 및 무작위 검색과 같은 기술의 앙상블을 사용하는 프레임워크의 한 예입니다.
01:10:00 이 섹션에서 발표자는 자동 조정의 개념과 Try에 대한 일정 생성에 적용할 수 있는 방법에 대해 설명합니다. 관련된 그래프와 리듬을 이해함으로써 자동 튜닝을 사용하여 전체 검색보다 더 효율적이고 효과적으로 일정을 생성할 수 있습니다. 이 방법은 2시간 이내에 스케줄을 생성할 수 있었고 경우에 따라 원래 가능한 최상의 스케줄이라고 생각했던 것보다 훨씬 더 나은 스케줄을 생성할 수 있었습니다.
"19. Leiserchess Codewalk"라는 제목의 이 YouTube 동영상에서 Helen Xu는 상대 팀의 왕을 쏘거나 자신의 왕을 쏘는 것을 목적으로 두 팀이 하는 게임인 Lesierchess의 규칙을 설명합니다. 이 게임에는 기본 및 스와트 동작의 두 가지 유형의 동작과 상대의 가장 최근 동작을 취소하면 동작을 불법으로 만드는 Ko 규칙이 있습니다. Xu는 Fisher 시간 제어 방법, Forsythe-Edwards 표기법, 클라우드 자동 테스터 및 프로젝트 구성, Elo 등급, 이동 생성, 정적 평가 및 알파-베타와 같은 검색 알고리즘을 사용하여 봇을 평가 및 비교하는 등 게임 플레이의 다양한 측면에 대해 자세히 설명합니다. 원칙 변형, 하위 트리 가지치기 및 전치 테이블. 그녀는 프로그램 최적화를 위한 테스트 인프라의 중요성과 조각 유형 및 색상을 기반으로 보드의 각 사각형을 평가하는 휴리스틱이 포함된 eval.c 파일에 대해서도 설명합니다.
연사는 또한 게임의 레이저 커버리지 측면에 대해 깊이 파고들어 플레이어의 색상에 따라 포지션에 대해 가능한 모든 동작을 생성하는 복잡한 시스템을 true라는 문장을 사용하여 설명합니다. 또한 코드의 정확성의 중요성과 이를 테스트하는 방법을 설명하고 성능을 최적화하기 전에 정확성을 보장하기 위한 표현 변환을 제안합니다. 연사는 또한 Leiserchess UCI 인터페이스가 제공하는 뛰어난 유연성에 대해 논의합니다. 이 인터페이스를 통해 사용자는 테이블과 명령을 원하는 대로 편집할 수 있으며 죽은 코드가 정리되고 다른 모든 버그는 수정된 것으로 보고되어야 한다고 시청자를 안심시킵니다.
00:00:00 이 섹션에서 Helen은 Lesierchess 게임의 규칙과 게임 방법을 안내합니다. 이 게임은 오렌지와 라벤더의 두 팀으로 진행되며 각 팀에는 7개의 폰과 킹이 있습니다. 이 게임의 목적은 상대 팀의 왕을 쏘거나 당신의 왕을 쏘는 것입니다. 이 게임에는 기본 및 스와트 동작의 두 가지 유형의 동작이 있습니다. 이 게임에는 상대 팀이 있던 곳으로 다시 이동하여 상대의 가장 최근 이동을 취소하면 이동을 불법으로 만드는 Ko 규칙이 있습니다. 폰이 재핑되지 않고 각 팀이 50번 이동했거나 같은 위치가 반복되거나 두 팀이 무승부에 동의하면 무승부가 발생합니다.
00:05:00 이 섹션에서는 화자가 Leiserchess에서 사용하는 Fisher 시간 제어 방법을 설명합니다. 각 플레이어는 초기 시간 예산과 시간 증분으로 시작합니다. 사용된 예에서 각 플레이어는 60초로 시작하고 이동을 종료하면 0.5초가 추가됩니다. 그러나 실제 시간 제한은 무엇이든 될 수 있습니다. 그런 다음 연사는 청중에게 반격을 피하면서 F5에서 폰을 찌르는 탠저린의 동작을 제안하도록 요청하여 레저체스를 플레이하는 방법을 시연합니다. 그러나 화자는 순진하게 모든 조각을 죽이는 것과 같은 게임의 미묘함에 대해 경고합니다.
00:10:00 이 섹션에서 Helen Xu는 문자열을 사용하여 체스 위치를 나타내는 도구로서 Forsythe-Edwards 표기법에 대해 설명합니다. 이는 디버깅 목적에 유용하며 특정 위치로 쉽게 돌아갈 수 있습니다. 그녀는 또한 체스 게임의 로그를 읽는 방법을 설명하며 각 이동과 해당 주석을 세분화합니다. 또한 그녀는 스크리미지 서버를 사용하여 수업의 다른 팀과 함께 봇을 테스트하는 방법과 다른 팀에 도전하고 경기를 보는 방법을 시연합니다.
00:15:00 이 섹션에서는 Helen Xu가 Lesierchess의 클라우드 자동 테스터 및 프로젝트 구성에 대해 설명합니다. 스크리미지 서버는 한 번에 하나의 게임만 허용하지만 클라우드 자동 테스터는 각 사용자의 기본 설정에 따라 사용자 지정할 수 있는 시간 제어에서 여러 게임과 바이너리를 실행할 수 있습니다. 저장소의 프로젝트 조직에는 doc, auto tester, pgnstates, tests, player 및 webgui 디렉토리가 포함됩니다. 자동 테스터는 로컬에서 변경 사항을 테스트하는 데 사용되는 Java 로컬 자동 테스터이며 테스트 디렉토리에서 자동 테스트를 위한 구성을 지정할 수 있습니다. Helen Xu는 또한 Lesierchess가 자동 테스터와의 인터페이스에 사용하는 통신 프로토콜인 UCI(Universal Chest Interface)를 소개합니다.
00:20:00 이 섹션에서 발표자는 제로섬 게임의 상대적 기술 수준을 기반으로 한 등급 시스템인 Elo 등급을 사용하여 봇을 측정하고 비교하는 방법에 대해 설명합니다. Elo 등급은 시간만을 기준으로 하는 것이 아니라 UCI를 사용하여 검색한 초당 노드도 기준으로 합니다. 그런 다음 발표자는 동작 생성, 보드 표현 및 위치를 저장하는 데 사용되는 구조체와 같은 게임 플레이에 대해 자세히 설명합니다. 또한 이동은 조각 유형, 방향, 정사각형, 중간 정사각형 및 두 정사각형을 포함하는 28비트를 사용하여 표현됩니다. 참조 주입은 보드를 반복하고 해당 특정 부분에서 모든 동작을 생성하여 누구의 차례인지에 따라 모든 동작을 생성합니다. 화자는 디버깅 함수 perft를 사용하여 수정된 이동 생성이 각 위치에서 동일한 이동을 반환하도록 보장한다고 언급합니다.
00:25:00 이 섹션에서 발표자는 휴리스틱을 사용하여 위치를 기반으로 점수를 생성하는 정적 평가를 통해 이동이 좋은지 확인하는 방법에 대해 설명합니다. 휴리스틱에는 킹, 폰 및 거리에 초점을 맞춘 것이 포함되며 위치가 좋은지 여부를 결정하는 데 도움이 될 수 있습니다. 연사는 또한 게임 플레이 프로그램이 검색 트리를 사용하여 게임을 플레이하고 평가를 기반으로 최상의 수를 선택하는 방법에 대해 이야기합니다. 노드 수를 줄이기 위해 발표자는 정지 검색 및 최소-최대 검색에 대해 자세히 설명합니다. 이는 평가되는 노드의 양을 개선하고 더 나은 성능으로 이어질 수 있습니다.
00:30:00 이 섹션에서 발표자는 윈도우 알파 베타가 있는 노드에서 검색하는 동안 사용되는 알파 베타라는 알고리즘에 대해 설명합니다. 검색 값이 알파 이하로 떨어지면 이동이 충분하지 않고 계속 검색합니다. 베타는 본질적으로 한쪽은 최대화하려고 하고 한쪽은 최소화하려고 한다는 것을 의미합니다. 따라서 값이 베타보다 높으면 상대가 너무 좋은 움직임을 허용하지 않기 때문에 베타 컷오프를 생성합니다. 그런 다음 연사는 첫 번째 이동이 최선이라고 가정하는 기본 변형 검색을 설명하고 나머지 이동에 대해 제로 창 검색이라고도 하는 스카우트 검색을 실행하여 더 나쁜지 확인합니다. 이 검색 방법은 알파-베타 알고리즘의 변형입니다.
00:35:00 이 섹션에서는 minimax 검색 알고리즘의 하위 트리 가지치기 개념에 대해 설명합니다. 하위 트리 가지치기의 기본 개념은 지금까지 발견된 최고 점수보다 낮은 점수를 가진 하위 트리를 제거하는 것입니다. 이렇게 하면 평가되는 노드 수가 줄어들고 검색 프로세스 속도가 빨라집니다. 상대방도 최선의 움직임을 찾고 플레이어의 점수를 최소화하려고 합니다. 플레이어의 점수를 극대화하는 것과 상대방의 점수를 최소화하는 것 사이의 균형이 중요하며, 목표는 플레이어에게 좋은 움직임과 상대방이 허용할 수 있는 동작을 찾는 것입니다.
00:40:00 이 섹션에서 Helen Xu는 가장 왼쪽 하위 트리가 최상의 경로이고 가정이 참인 경우 조기 종료가 수행된다는 가정을 하는 주요 변형 가지치기의 개념을 설명합니다. 가정이 거짓이면 전체 하위 트리를 검색해야 합니다. Scout 검색은 가정을 확인하기 위한 초기 패스와 함께 이를 하위 하위 트리에 재귀적으로 적용하는 데 사용됩니다. 이 방법은 가지치기를 개선하고 제로 창 검색으로 대부분의 게임 트리를 처리합니다.
00:45:00 이 섹션에서는 Leiserchess 프로그램의 검색 최적화에 대해 알아봅니다. 가장 중요한 최적화 중 하나는 전치 테이블을 사용하여 이전에 발생한 위치를 저장하여 불필요한 검색을 피함으로써 시간을 절약하는 것입니다. 다른 최적화에는 각 위치에 대한 고유한 해시를 생성하는 Zobrist 해싱 사용, 재계산할 필요가 없도록 좋은 동작을 저장하는 킬러 이동 테이블, 알파 점수를 높이지 않는 동작 탐색을 건너뛰는 무익성 가지치기가 포함됩니다. 게임 시작 시 미리 계산된 위치를 저장하고 검색 시간을 절약하기 위해 더 나은 시작 책을 구현하는 것도 권장됩니다.
00:50:00 이 섹션에서 연사는 미리 계산할 수 있는 책 열기 및 최종 게임 데이터베이스를 포함하여 체스 프로그램을 최적화하는 몇 가지 유용한 도구에 대해 설명합니다. 디버깅 문제 없이 혁신하고 발전할 수 있도록 테스트하고 좋은 테스트 인프라를 갖추는 것이 중요합니다. 병렬 프로그래밍에서 전치 테이블을 사용하면 테스트 목적으로 테이블을 끌 수 있는 것이 중요하며 테스트할 때 고정 깊이 검색을 수행하는 것이 좋습니다. 전반적으로 좋은 테스트 인프라를 갖추는 것은 진전을 이루고 중요한 디버깅 문제를 피하는 데 중요합니다.
00:55:00 이 섹션에서 발표자는 Leiserchess 프로젝트의 eval.c 파일과 그 크기와 복잡성으로 인해 언뜻 보기에 어떻게 압도적으로 보일 수 있는지에 대해 논의합니다. 그러나 사용자가 이에 익숙해지면 적절한 크기의 코드를 처리하는 데 자신감을 갖게 됩니다. eval.c 파일에는 조각의 유형과 색상을 기반으로 보드의 각 사각형을 평가하는 p between, p central, k face 및 k attack과 같은 휴리스틱이 포함되어 있습니다. 휴리스틱 간 p는 폰이 두 왕 사이에 있는지 여부를 결정하는 반면 p central은 폰이 보드 중앙에 얼마나 가까운지에 따라 보너스를 제공합니다. k면 및 k 공격적 휴리스틱은 킹의 방향과 상대 및 보드 가장자리로부터의 거리에 따라 보너스를 제공합니다.
01:00:00 이 섹션에서는 화자가 게임의 복잡한 측면인 레이저 범위에 대해 설명합니다. 레이저 범위는 플레이어의 색상에 따라 특정 위치에서 가능한 모든 이동을 생성합니다. 그런 다음 이동 목록을 제공하고 화자는 이 지도가 while-true 문으로 기능을 수행하는 방법을 자세히 설명합니다. 레이저 경로는 경로를 그리는 동안 일부 폰에서 튕겨져 각 사각형의 거리를 늘립니다. 지도를 생성한 후 과정을 반복하고 그 거리를 레이저로부터의 실제 거리로 나눕니다. 이 복잡한 시스템은 보드의 각 조각을 찾는 평가 방법에 필요한 반복을 최적화하여 프로세스 속도를 늦추고 발표자는 보드를 다르게 표현하고 두 변환 함수가 동일한 결과를 산출한다고 주장하는 것이 좋은 방법이라고 덧붙입니다. 최적화 결정.
01:05:00 비디오의 이 섹션에서 연사는 코드의 정확성 유지의 중요성과 이를 테스트하는 방법에 대해 논의합니다. 한 표현에서 다른 표현으로 변환하면 프로세스 속도가 느려질 수 있지만 성능을 최적화하기 전에 정확성을 보장하는 데 필요하다고 설명합니다. 정확성을 테스트하는 한 가지 방법은 노드 수를 추적하고 변경 후에도 동일하게 유지되는지 확인하는 것입니다. 또한 코드를 실행하는 방법과 Lesierchess.c에서 UCI 인터페이스를 표시하여 매번 바이너리를 다시 컴파일하지 않고도 다양한 항목에 대한 값을 설정할 수 있도록 합니다. 마지막으로 휴리스틱 테이블을 살펴보고 자동 테스터의 값을 지정하는 방법을 설명합니다.
01:10:00 이 섹션에서 연사는 Leiserchess 게임이 UCI 인터페이스를 통해 테이블과 명령을 편집할 때 제공하는 뛰어난 유연성에 대해 설명합니다. 이를 통해 사용자는 새로운 휴리스틱을 포함하여 원하는 모든 명령에 액세스하고 구현할 수 있으며 구문 분석 및 구현을 제어할 수 있습니다. 일부 죽은 코드가 존재하지만 교수는 시청자에게 코드가 정리될 것이며 다른 버그가 있으면 보고하여 수정해야 한다고 안심시킵니다. 마지막으로 그는 프로젝트가 매 순간 재미있지는 않을 수 있지만 전반적으로 많은 즐거움을 제공한다고 말합니다.
강의 10. 측정과 타이밍
강의 10. 측정과 타이밍
이 비디오에서 연사는 정확도에 영향을 미칠 수 있는 외부 요인을 포함하여 컴퓨팅에서 측정 및 타이밍의 다양한 측면에 대해 논의합니다. 그들은 모델의 필요성과 데이터에 대한 명확한 이해, 오류를 보상하기 위한 분산 감소, 신뢰성을 보장하기 위한 적절한 타이밍 호출 사용을 강조합니다. 또한 성능 모델링, 타이밍 호출, 하드웨어 카운터 및 시뮬레이터와 같은 도구를 강조하면서 전력 법칙 및 비결정론적 요인과 같은 소프트웨어 성능을 정확하게 측정하는 데 따르는 문제에 대해 논의합니다. 마지막으로 그들은 정확한 결과를 보장하기 위한 기술로 삼각 측량 및 적응을 권장하면서 단일 도구에 의존하지 않도록 주의합니다.
연사는 성능 소프트웨어 엔지니어링에서 신뢰할 수 있는 성능 측정의 중요성을 설명합니다. 그는 통계를 사용하여 성능을 정확하게 측정할 것을 권장하고 다양한 상황에서 유용한 성능 측정을 제공할 수 있는 평균과 같은 다양한 유형의 요약 통계에 대해 설명합니다. 그는 비율의 산술 평균을 취하는 것이 유효한 접근 방식이 아니라고 지적하고 대신 기하 평균을 사용할 것을 제안합니다. 연사는 프로그램을 비교할 때 데이터를 집계하는 올바른 방법을 선택하는 것의 중요성을 강조하고 성능을 보다 정확하게 비교하기 위해 여러 실행에서 최소 또는 10%와 같은 낮은 차수 통계를 취할 것을 제안합니다. 연사는 또한 일대일 비교 및 통계 도출을 위한 모델 피팅을 포함하여 성능을 측정하고 비교하는 다양한 방법론에 대해 논의하지만 모델링의 과적합 문제에 대해 경고합니다. 전반적으로 비디오는 프로그램 성능 향상을 위한 신뢰할 수 있는 성능 측정의 중요성을 강조합니다.
강의 11. 스토리지 할당
강의 11. 스토리지 할당
강사는 이 비디오에서 메모리 할당과 해제를 모두 다루는 스토리지 할당에 대해 설명합니다. 고정 및 가변 크기 할당 체계뿐만 아니라 스택 및 힙을 포함하여 다양한 유형의 스토리지가 처리됩니다. 사용 가능한 목록 또는 디스크 페이지당 비트맵과 같은 솔루션을 사용하여 분산되는 메모리 블록으로 인해 발생하는 외부 조각화에 대해서도 설명합니다. 참조 카운팅 및 이 알고리즘의 한계를 포함하여 가비지 수집의 개념도 소개됩니다. "표시 및 스윕" 및 "정지 및 복사" 가비지 수집 절차도 설명되며, 후자가 조각화를 해결하는 방법과 포인터 업데이트로 인해 발생할 수 있는 정확성 문제에 중점을 둡니다. 비디오는 중지 및 복사 알고리즘의 시간 및 공간 복잡성과 외부 조각화 제거에 대한 메모로 끝납니다.
이 비디오는 Buddy 시스템, 표시 및 스윕 절차, 최적화, 세대별 및 실시간 가비지 수집, 다중 스레드 저장소 할당 및 병렬 가비지 수집을 포함하여 동적 저장소 할당과 관련된 다양한 주제를 다룹니다. 강사는 세대별 가비지 컬렉션이 프로그램 실행 중에 백그라운드에서 실시간 가비지 컬렉션이 실행되는 동안 더 어린 객체가 더 자주 스캔된다는 아이디어를 기반으로 하지만 객체 및 포인터 그래프가 계속 변경되면 정확성 문제가 발생할 수 있다고 설명합니다. 마지막으로 이 강의에서는 스택 및 힙을 포함한 다양한 유형의 스토리지 할당과 참조 카운팅, 표시 및 스윕, 중지 및 복사와 같은 다양한 가비지 수집 방법을 요약합니다. 강사는 학생들이 다가오는 숙제에서 이러한 방법 중 일부를 시도하게 될 것이라고 언급합니다.
강의 12. 병렬 스토리지 할당
강의 12. 병렬 스토리지 할당
이 비디오에서는 다양한 메모리 할당 전략과 장단점에 대해 설명합니다. malloc 및 정렬된 할당의 사용과 free로 적절한 메모리 할당 해제의 중요성이 설명됩니다. 외부 조각화 및 느린 성능 문제와 함께 가상 메모리 할당을 위한 Mmap 사용도 다룹니다. 스택 프레임을 할당하기 위한 힙 기반 선인장 스택 접근 방식을 강조하여 C 및 C++ 프로그래밍의 스택 개념을 살펴보고 더 나은 공간 제한 증명 및 상한으로 이어질 수 있습니다. 조각화를 최소화하기 위해 작은 블록을 최적화하는 것의 중요성과 함께 선형 스택 풀의 사용에 대해서도 설명합니다. 이 비디오는 이러한 문제를 해결하기 위한 빈 사용 가능 목록 및 주기적인 메모리 재조정과 같은 접근 방식과 함께 글로벌 및 로컬 힙 접근 방식과 잠재적인 문제에 대한 논의로 끝납니다.
비디오는 또한 병렬 스토리지 할당을 위한 솔루션에 대해 설명하고 Hoard 할당자를 솔루션으로 소개합니다. Hoard 할당자는 잘못된 공유를 줄이고 확장성을 개선하며 외부 조각화를 줄이기 위해 힙 간에 이동할 수 있는 대형 수퍼 블록과 로컬 및 글로벌 힙의 조합을 사용합니다. 글로벌 힙에 할당된 최대 스토리지는 로컬 힙에 할당된 최대 스토리지이며, 풋프린트는 사용자 풋프린트와 로컬 힙에서 할당되었지만 사용되지 않은 스토리지의 상한입니다. 비디오는 또한 Je malloc 및 Super malloc과 같은 다른 할당자에 대해 간략하게 설명하며 벤치마크 결과는 Super malloc이 Je malloc 및 Hoard보다 성능이 더 우수함을 나타냅니다. 토론은 가비지 수집 세부 정보에 대한 온라인 슬라이드를 참조하는 것으로 끝납니다.
강의 13. Cilk 런타임 시스템
강의 13. Cilk 런타임 시스템
Cilk 런타임 시스템은 무작위 작업 도용 스케줄러를 사용하여 런타임 시 프로세서에 계산을 매핑하여 병렬 프로세서에서 계산을 예약하고 로드 밸런싱하는 역할을 합니다. 이 시스템은 도용에 대한 추가 비용이 발생하더라도 프로그램의 직렬 실행을 최적화하도록 설계되었습니다. 작업자는 스택 프레임에 대한 포인터를 포함하고 헤드 및 테일 포인터를 사용하는 별도의 데크 데이터 구조를 유지합니다. 훔칠 수 있는 프레임에는 데크가 호출 스택 외부에 있는 동안 훔치는 데 필요한 정보가 포함된 추가 로컬 구조가 있습니다. 이 섹션에서는 시스템이 프로세서가 실행 중인 함수의 중간에서 실행을 시작할 수 있도록 하는 방법과 특정 프로세서가 여전히 계산이 완료되기를 기다리고 있기 때문에 지점을 넘어 실행할 수 없는 동기화 문에 도달할 때 프로세서 간의 동기화가 복잡해지는 방법을 설명합니다. 또한 발표자는 시스템의 성능, 설계 고려 사항 및 데이터 구조, 시스템이 THC 프로토콜을 사용하여 실행을 최적화하는 방법에 대해 설명합니다. 여기에는 작업을 실행하는 작업자와 도둑을 위한 두 가지 프로토콜 세트가 포함됩니다.
Cilk Runtime System은 set jump 및 long jump 프로토콜을 사용하여 희생 프로세스의 실행 데크에서 계산 도용을 처리합니다. 캑터스 스택 추상화는 도둑 프로세스가 피해자 스택의 손상을 방지하기 위해 자체 호출 스택을 가질 수 있도록 합니다. 시스템의 동기화 프로토콜은 계산 트리와 Cactus 스택을 사용하여 동기화가 함수 내의 중첩된 계산 사이에서만 발생하도록 합니다. 전체 프레임 트리는 동기화 프로세스를 단순화하기 위해 뛰어난 하위 계산이 있는 계산 간의 부모-자식 관계를 유지합니다. 또한 런타임 시스템은 현재 함수에 미해결 자식 계산이 없고 모든 작업자가 바쁜 일반적인 경우를 최적화합니다. 지원되는 다른 기능으로는 C++ 예외, 감속기 하이퍼 개체 및 혈통이 있습니다.
강의 14. 캐싱 및 캐시 효율적 알고리즘
강의 14. 캐싱 및 캐시 효율적 알고리즘
캐싱 및 캐시 효율적인 알고리즘에 대한 비디오에서 강사는 최신 시스템의 캐시 계층 구조, 완전 연관 캐시와 직접 매핑 캐시의 차이점, 세트 연관 캐시의 장단점을 설명합니다. 비디오는 또한 이상적인 캐시 모델과 캐시 효율적인 알고리즘의 개념을 소개합니다. 발표자는 캐시 미스 기본형, tall형 캐시 가정 및 하위 행렬 캐싱 기본형에 대해 설명합니다. 또한 하위 행렬을 읽을 때와 행렬 곱셈 중에 발생한 캐시 미스를 분석합니다. 비디오는 타일 행렬 곱셈의 개념과 성능을 크게 향상시킬 수 있는 방법을 소개하면서 결론을 내리지만, 이식성이 없으며 여러 수준의 캐시에 대해 최적화하는 데 비용이 많이 들 수 있다는 점도 언급합니다.
강의에서는 재귀 행렬 곱셈을 예로 들어 캐싱 및 캐시 효율적인 알고리즘을 다룹니다. 발표자는 작업 및 캐시 미스를 개별적으로 분석하는 것의 중요성을 강조하고 캐시 인식 알고리즘이 캐시 크기가 다르기 때문에 모든 시스템에 최적이 아닐 수 있음을 언급합니다. 발표자는 또한 모든 캐시 크기에 맞게 자동 조정되는 캐시 무시 알고리즘에 대해 논의하고 병렬 캐시 무시 코드의 개발을 언급합니다. 마지막으로 목표는 캐시를 인식하거나 캐시를 무시하는 알고리즘을 설계하는 것이며 캐시를 무시하는 알고리즘 설계에 대한 논의는 다음 강의에서 계속됩니다.
강의 15. Cache-Oblivious 알고리즘
강의 15. Cache-Oblivious 알고리즘
이 비디오에서는 머신의 캐시 크기를 자동으로 조정하고 우수한 캐시 효율성을 달성하며 머신의 캐시 매개변수에 대한 지식이 필요하지 않은 캐시 무시 알고리즘에 대해 설명합니다. 영상은 2D 매트릭스에서 스텐실 방법을 사용하여 미분 방정식을 통해 열 확산을 시뮬레이션하는 코드를 작성하는 방법을 보여줍니다. 이 코드에는 루핑 및 사다리꼴 버전이 모두 있으며 후자는 캐시 효율성이 더 높지만 루핑 코드 액세스 패턴의 예측 가능성으로 인해 2D 시뮬레이션에서 훨씬 빠르지는 않습니다. 비디오는 또한 캐싱과 병렬 처리 간의 상호 작용과 잠재적인 병렬 속도 향상 병목 현상 진단에 대해 설명합니다. 마지막으로 발표자는 스텐실 계산과 스텐실이라는 고정 패턴을 사용하여 어레이의 각 포인트가 업데이트되는 방법에 대해 설명합니다. 스텐실은 캐시 누락이 발생할 수 있으며 시간적 및 공간적 지역성을 활용하는 효율적인 알고리즘을 사용하여 스토리지 요구 사항을 줄일 수 있습니다.
비디오의 두 번째 부분에서는 정렬 및 병합을 위한 캐시 인식 알고리즘에 대해 설명합니다. 특히, 비디오는 병합 정렬의 캐시 복잡성을 다루고 다중 방식 병합의 개념을 소개하며 다중 방식 병합 알고리즘의 캐시 복잡성을 설명합니다. 이 동영상에서는 K 제곱 요소와 K 정렬 목록을 병합할 수 있는 캐시 무시 정렬 알고리즘인 깔때기 정렬 알고리즘에 대해서도 설명합니다. 깔때기 정렬 알고리즘은 최적이며 K 깔때기의 제곱근으로 재귀적으로 구성됩니다. 비디오는 b-트리, 순서가 지정된 파일 유지 관리 및 우선 순위 대기열과 같은 다른 많은 캐시 인식 알고리즘 및 데이터 구조가 있다고 설명합니다. 전반적으로 이 비디오는 주제에 대해 자세히 알아보는 데 관심이 있는 사람들을 위해 캐시를 무시하는 알고리즘에 대한 소개를 제공합니다.
강의 16. 비결정적 병렬 프로그래밍
강의 16. 비결정적 병렬 프로그래밍
이 비디오는 결정론적 및 비결정론적 병렬 프로그래밍과 관련된 다양한 개념에 대해 설명합니다. 연사는 비정상적인 동작과 어려운 디버깅으로 이어질 수 있으므로 비결정론을 피하는 것의 중요성을 강조합니다. 비결정성을 관리하기 위한 전략에는 고정 값 사용, 레코드 재생, 분석 도구, 캡슐화 및 단위 테스트가 포함됩니다. 회전 대 양보, 재진입 대 비재진입, 공정 대 불공평을 포함하여 뮤텍스의 사용을 자세히 살펴봅니다. 연사는 또한 병렬 프로그래밍의 맥락에서 맥락 전환의 개념과 "스키 대여 문제"에 대해서도 언급합니다. 이 세그먼트는 멀티 코어 프로세서에서 성능 엔지니어링의 기본 원칙을 논의하면서 끝납니다.
비디오의 두 번째 부분에서는 병렬 프로그래밍의 교착 상태 문제를 다루고 대기 주기가 없도록 보장하는 뮤텍스의 선형 순서 지정과 같이 교착 상태를 방지하는 솔루션을 제공합니다. 또한 발표자는 중요한 영역을 모든 업데이트를 한 번에 커밋하는 트랜잭션으로 표현하여 원자성을 보장하는 트랜잭션 메모리의 개념을 소개합니다. 그런 다음 비디오는 유한 소유권 배열과 함께 잠금 기반 접근 방식을 사용하는 알고리즘과 글로벌 잠금 없이 교착 상태 및 기아 상태를 방지하기 위한 릴리스 정렬 필요 메서드를 제시합니다. 마지막으로 알고리즘 릴리스 정렬 및 재취득에 대해 설명합니다. 이는 여러 잠금이 동시에 잠금을 획득하려고 시도하지 않도록 하여 성능 문제를 방지합니다.
강의 17. 잠금 없는 동기화
강의 17. 잠금 없는 동기화
Charles Leiserson은 YouTube 동영상에서 잠금 없는 동기화의 개념을 탐구합니다. 그는 순차 실행을 보장하기 위해 명령의 전역 선형 순서의 필요성을 보여주는 예를 제공하고 잠금 사용의 어려움과 잠재적인 문제를 피하면서 순차 일관성을 통해 상호 배제를 달성할 수 있는 방법에 대해 설명합니다. Leiserson은 Peterson의 알고리즘을 로드 및 저장 작업만 사용하여 동시 프로세스의 간섭 없이 중요 섹션에 액세스하는 솔루션으로 제시합니다. 비디오는 또한 하드웨어 재정렬로 인한 메모리를 통한 동기화 문제와 다른 명령과의 상대적인 순서를 유지하기 위한 메모리 펜스의 개념을 다룹니다. Leiserson은 병렬 시스템에 대한 순차적 일관성을 지원하는 것이 유익하지만 하드웨어 설계자에게는 달성하기 어렵다고 주장합니다.
비디오의 두 번째 부분에서는 병렬 프로그램의 오류를 방지하기 위한 메모리 펜스와 동기화 명령의 사용에 대해 설명합니다. 발표자는 메모리 펜스를 암시적으로 또는 명시적으로 구현하는 다양한 방법과 프로세서의 다양한 측면에서 작업하는 여러 팀 간의 신중한 엔지니어링 및 조정의 중요성을 탐구합니다. 또한 강사는 C11 언어 표준에서 잠금 해제 알고리즘의 일부로 CAS 명령어를 사용하여 상수 공간만 사용하여 n-스레드 교착 상태가 없는 상호 배제 알고리즘의 뮤텍스를 구현하는 방법에 대해 설명합니다. Charles Leiserson은 다중 스레드 시스템에서 잠금을 사용하는 문제와 대신 CAS를 사용하는 솔루션에 대해 설명합니다. 잠금을 오랫동안 유지하는 스레드는 동일한 리소스에 액세스하기 위해 대기 중인 다른 스레드를 잠재적으로 차단할 수 있기 때문입니다. 또한 비디오는 비교 및 교환과 관련된 ABA 문제의 잠재적인 문제를 강조하고 주제에 관심이 있는 사람들이 잠금 해제 알고리즘에 대해 자세히 알아보도록 권장합니다.
강의 18. 도메인 특정 언어 및 자동 튜닝
강의 18. 도메인 특정 언어 및 자동 튜닝
이 비디오에서 MIT EECS 부서의 Saman Amarasignhe 교수는 성능 엔지니어링에서 DSL(도메인별 언어) 사용 및 자동 튜닝의 이점에 대해 설명합니다. 그는 범용 언어로 설명하기 어려운 영역별 도메인을 캡처하여 프로그래머가 더 나은 성능을 위해 도메인 전문가의 지식을 활용할 수 있도록 하는 DSL의 중요성을 강조합니다. Singh은 그래프 파티셔닝 및 계산에서 그래프 모양의 중요성을 포함하여 DSL을 사용한 그래프 프로세스의 최적화에 대해 논의합니다. 그는 이미지 처리를 위한 DSL Halide를 소개합니다. 이는 빠른 코드 최적화와 시스템 간 이식성을 가능하게 합니다. 그는 Google 및 Adobe와 같은 다양한 산업에서 Halide의 사용에 대해 논의합니다. 궁극적으로 그는 병렬성, 지역성 및 중복 작업에 초점을 맞추면서 코드를 최적화하는 다양한 접근 방식을 실험하는 것의 중요성을 강조합니다.
비디오는 또한 성능 엔지니어링의 문제와 프로그램이 효율적으로 실행되기 위한 최적의 매개변수를 찾는 문제에 대해 설명합니다. 발표자는 자동 튜닝이 최적의 값을 찾기 위해 큰 매개변수 공간을 자동으로 검색하여 이 문제를 해결할 수 있다고 제안합니다. 그는 철저한 검색이 비실용적일 수 있으며 휴리스틱 기반 솔루션이 최적이 아닐 수 있다고 지적합니다. 허용 가능한 값의 공간을 정의하고 성능 결과를 기반으로 반복하는 자동 튜닝은 최적의 솔루션을 찾는 프로세스를 가속화할 수 있습니다. 연사는 또한 전체 검색보다 더 효율적이고 효과적으로 일정을 생성할 수 있는 Try의 일정 생성에 자동 튜닝을 적용하는 방법에 대해 설명합니다.
강의 19. Leiserchess 코드워크
강의 19. Leiserchess 코드워크
"19. Leiserchess Codewalk"라는 제목의 이 YouTube 동영상에서 Helen Xu는 상대 팀의 왕을 쏘거나 자신의 왕을 쏘는 것을 목적으로 두 팀이 하는 게임인 Lesierchess의 규칙을 설명합니다. 이 게임에는 기본 및 스와트 동작의 두 가지 유형의 동작과 상대의 가장 최근 동작을 취소하면 동작을 불법으로 만드는 Ko 규칙이 있습니다. Xu는 Fisher 시간 제어 방법, Forsythe-Edwards 표기법, 클라우드 자동 테스터 및 프로젝트 구성, Elo 등급, 이동 생성, 정적 평가 및 알파-베타와 같은 검색 알고리즘을 사용하여 봇을 평가 및 비교하는 등 게임 플레이의 다양한 측면에 대해 자세히 설명합니다. 원칙 변형, 하위 트리 가지치기 및 전치 테이블. 그녀는 프로그램 최적화를 위한 테스트 인프라의 중요성과 조각 유형 및 색상을 기반으로 보드의 각 사각형을 평가하는 휴리스틱이 포함된 eval.c 파일에 대해서도 설명합니다.
연사는 또한 게임의 레이저 커버리지 측면에 대해 깊이 파고들어 플레이어의 색상에 따라 포지션에 대해 가능한 모든 동작을 생성하는 복잡한 시스템을 true라는 문장을 사용하여 설명합니다. 또한 코드의 정확성의 중요성과 이를 테스트하는 방법을 설명하고 성능을 최적화하기 전에 정확성을 보장하기 위한 표현 변환을 제안합니다. 연사는 또한 Leiserchess UCI 인터페이스가 제공하는 뛰어난 유연성에 대해 논의합니다. 이 인터페이스를 통해 사용자는 테이블과 명령을 원하는 대로 편집할 수 있으며 죽은 코드가 정리되고 다른 모든 버그는 수정된 것으로 보고되어야 한다고 시청자를 안심시킵니다.