RAM 모델의 동기는 무엇입니까?

Aug 17 2020

오늘날 알고리즘 분석의 대부분은 단어 RAM 모델과 같이 일정 시간 랜덤 액세스가있는 모델에서 수행되는 것 같습니다. 나는 물리학에 대해 잘 모르지만 인기있는 출처에서 볼륨 당 정보 저장 및 정보 이동 속도에 제한이 있어야한다고 들었 기 때문에 RAM은 물리적으로 실현할 수없는 것 같습니다. 현대 컴퓨터에는 이러한 모든 캐시 수준이 있으므로 RAM과 비슷하지 않습니다. 그렇다면 왜 이론적 알고리즘이 RAM에 설정되어야합니까?

답변

3 6005 Aug 18 2020 at 13:47

vonbrand와 다른 방식으로 설명하겠습니다. 당신이 말한 모든 것이 사실입니다. RAM 모델은 여러 가지 이유로 현실적이지 않으며, 다른 측면을 방어 할 수 있지만 그러한 방어는 문제의 핵심에 도달하지 않습니다.

문제의 핵심과 귀하의 질문에 대한 답은 RAM 모델이 우리가 가지고있는 최고의 제품이라는 것입니다. 허용되는 다른 모델에 비해 실제 계산을 더 정확하게 모델링합니다. 특히, 우리가 RAM 모델을 채택한 이유는 주로 Turing 기계에 대한 대응이었습니다. Turing 기계를 사용하면 시간 복잡성 측면에서 인위적으로 해결하기 어려운 문제가 발생한다는 것을 알 수 있었기 때문입니다. RAM 모델은이 눈부신 문제를 명확하게 해결하므로 완벽하지는 않지만 여전히 받아 들여졌습니다.

Turing 머신의 눈부신 문제를 보여주는 고전적인 예는 문자열 평등 문제입니다.

$$ w_1 \# w_2$$

어디 $w_1, w_2$ 이진 시퀀스이고 $\#$ 구분 기호이며 $w_1 = w_2$. 평등 문제에 대한 모든 튜링 기계는$O(n^2)$시각. 튜링 머신은 모두가 보편적 인 계산 모델로 생각하는 것이기 때문에 불편합니다.하지만 소프트웨어 엔지니어 나 알고리즘 연구원은 문자열 평등이 실제로 필요하다고 생각하지 않습니다.$O(n^2)$시각. 그래서 무엇을 제공합니까? 문자열 평등은 선형이어야합니다. 그래서 우리는 그것이있는 곳에서 새로운 모델을 발명하고 현재 사용 가능한 최고의 솔루션은 워드 RAM 머신입니다.

아마도 언젠가 우리는 더 나은 모델을 만들 것입니다. 간단하고 개념적으로 명확하며 실제 계산 복잡성을 모델링하는 능력에서 RAM을 향상시키는 모델입니다. 지금은 우리가 가진 최선을 다할 수밖에 없습니다.

1 vonbrand Aug 17 2020 at 23:02

첫 번째, 대략적인 근사치로, 이전 액세스와 무관하게 일정하게 메모리의 단어에 액세스하는 데 시간을 할애 할 수 있습니다. 즉, RAM 모델입니다.

맞습니다. 오늘날의 머신은 RAM과 매우 유사합니다. 데이터 액세스를 가능한 한 순차적으로 구성하거나 맨 처리하기 전에 (짧은!) 메모리 세그먼트에서 마지막 정보를 짜내는 것이 (심지어 멋지게도) 효과가 있습니다. 다음. 그러나 그렇게 할 여지가 거의 없으며 메모리 액세스는 본질적으로 무작위이며 모델은 진실과 그리 멀지 않습니다. 게다가 오늘날의 컴퓨터에는 둘 이상의 CPU가 있고 모델에는 하나만 있습니다. 그리고 "멀티미디어 명령"(그리고 처리를 위해 그래픽 카드를 더 많이 사용하는 것)과 같은 벡터 처리 (데이터 벡터에 대해 하나씩가 아니라 동일한 작업을 수행함)가 있습니다.

예를 들어 Khoung의 Binary search는 캐시에 대한 병리학적인 사례입니다 . 보시다시피보다 현실적인 메모리 액세스 시간 모델에서 간단하고 잘 이해 된 알고리즘을 분석하는 것은 어렵습니다.

1 DmitriUrbanowicz Aug 19 2020 at 10:19

RAM 모델은 단일 스레드 인 메모리 계산으로 설계된 알고리즘의 점근 적 분석에 의해 동기가 부여됩니다.

특정 명령어 세트, 캐시 및 기타 사항에 대한 성능을 최적화하는 것은 한 가지입니다. 다른 하나는 문제 규모의 성장에 대비하는 것입니다. 인 메모리 알고리즘이 얼마나 잘 확장되는지 추정하려면 작은 요인을 무시하고 큰 요인에 집중할 수 있습니다.$\mathcal{O}$표기법. 큰$\mathcal{O}$ 모든 것을 최적화하지는 않지만 적어도 솔루션이 잘 확장된다는 것을 알려줄 수 있습니다 (또는 다른 것을 시도해야 함).

RAM은 각 작업이 작동하는 작은 고정 명령 세트를 가정합니다. $\mathcal{O}(1)$. 점근 적 성장에만 관심이있는 경우 이것은 좋은 모델입니다.