메모리 바인딩 함수

Memory-bound function

메모리 바인딩(Memory bounded)은 주어진 연산 문제를 완료하는 시간이 주로 작업 데이터를 저장하는 데 필요한 메모리 양에 의해 결정되는 상황을 말한다.이는 기본 계산 단계의 수가 결정 요인이 되는 계산 바인딩된 알고리즘과는 대조적이다.

메모리 및 연산 경계는 예비 결과를 저장 및 재사용하거나 룩업 테이블을 사용하여 서로 교환할 수 있다.

메모리 바인딩 기능 및 메모리 기능

메모리 바인딩 기능과 메모리 기능은 둘 다 광범위한 메모리 액세스를 수반한다는 점에서 관련이 있지만, 둘 사이에 차이가 존재한다.

메모리 기능은 발생할 수 있는 재귀의 비효율성을 해소하기 위해 메모화라는 동적 프로그래밍 기법을 사용한다.하위 문제를 다시 계산하지 않고 나중에 재사용할 수 있도록 하위 문제에 대한 솔루션을 계산하고 저장한다는 단순한 발상에 따른 것이다.메모화를 이용하는 가장 잘 알려진 예는 피보나치 숫자를 계산하는 알고리즘이다.다음 유사코드는 재귀와 메모화를 사용하며, 선형 CPU 시간으로 실행된다.

 피보나치 (n)  {      을 위해 i = 0 로 n-1          결과.[i] = -1  // -1은 정의되지 않은 것을 의미한다.       돌아오다 피보나치_결과 (결과., n);  }   피보나치_결과 (결과., n)  {      만일 (결과.[n] != -1)  // 전에 해결되었다면,          돌아오다 결과.[n]  // 찾아봐.      만일 (n == 0)          발랄하게 하다 = 0      다른 만일 (n == 1)          발랄하게 하다 = 1      다른          발랄하게 하다 = 피보나치_결과(결과., n-2 ) + 피보나치_결과(결과., n-1)      결과.[n] = 발랄하게 하다  // 재사용을 위해 이 결과를 저장한다.       돌아오다 발랄하게 하다  }

위의 내용을 재귀만 사용하고 지수 CPU 시간으로 실행되는 알고리즘과 비교해 보십시오.

 재귀_피보나치 (n)  {      만일 (n == 0)          돌아오다 0      만일 (n == 1)          돌아오다 1       돌아오다 재귀_피보나치 (n-1) + 재귀_피보나치 (n-2)  }

재귀 전용 알고리즘은 재귀와 메모화를 사용하는 알고리즘보다 간단하고 우아하지만, 후자는 전자에 비해 시간 복잡성이 현저히 낮다.

"메모리 바인딩 함수"라는 용어는 최근에야 표면화되었고 주로 XOR를 사용하는 함수를 기술하는데 사용되며, 각 연산이 이전 연산에 의존하는 일련의 연산들로 구성되어 있다.메모리 기능은 시간 복잡성을 개선하는 데 있어 오랫동안 중요한 행위자였지만, 메모리 결합 기능은 훨씬 적은 수의 응용 프로그램을 보아왔다.하지만 최근[when?] 과학자들은 스팸메일 발송자들이 자원을 남용하지 못하도록 하기 위한 수단으로 메모리 바인딩 기능을 사용하는 방법을 제안했는데, 이것은 이 분야에서 중요한 돌파구가 될 수 있다.

메모리 바인딩 기능을 사용하여 스팸 방지

메모리 바인딩 기능은 스팸을 억제할 수 있는 작업증명 시스템에서 유용할 수 있으며, 이는 인터넷에서 유행하는 비율의 문제가 되었다.

1992년 IBM의 연구 과학자 신시아 드워크와 모니 나오르는 CRYPTO 1992에서 '정크 메일 처리 또는 격투를 통한 가격 책정'이라는 제목의 논문을 발표하여,[1] 오용자의 스팸 발송을 막기 위해 CPU 바인딩 기능을 사용할 가능성을 시사했다.이 계획은 컴퓨터 사용자들이 자원을 남용하는 비용이 무시해도 될 정도라면 자원을 남용할 가능성이 훨씬 더 높다는 생각에 바탕을 두고 있다. 스팸메일이 횡행하게 된 근본적인 이유는 스팸메일 발송에 드는 비용이 아주 적기 때문이다.

Dwork와 Naor는 값비싼 CPU 계산의 형태로 추가 비용을 투입함으로써 스팸을 줄일 수 있다고 제안했다: CPU 바인딩 기능은 각 메시지에 대해 송신자의 기계에서 CPU 자원을 소비하므로 단기간에 엄청난 양의 스팸이 전송되는 것을 막을 수 있다.

남용으로부터 보호하는 기본방안은 다음과 같다.
S를 보낸 사람으로 하고, R을 받는 사람으로 하고, M을 e-메일로 하자.만약 R이 S로부터 이메일을 받기로 사전에 동의했다면, M은 통상적인 방법으로 전송된다.그렇지 않으면 S는 일부 함수 G(M)를 계산하여 R로 송신한다(M, G(M)).R은 S로부터 받은 것이 형태(M, G(M))인지 확인하고, 만약 그렇다면 R은 M을 받아들인다.그렇지 않으면 R은 M을 거부한다.오른쪽 그림은 사전 합의가 없었던 경우를 그렸다.

함수 G()는 R에 의한 검증이 비교적 빠르며(밀리초가 소요됨), S에 의한 계산이 다소 느리게(적어도 몇 초가 소요됨)되도록 선택된다.따라서 S는 사전 합의 없이 여러 수신자에게 M을 보내는 것을 꺼리게 될 것이다: 컴퓨팅 G()의 시간과 계산 자원에 관한 비용은 수백만 개의 이메일을 보내려는 스팸 발송자에게 반복적으로 매우 금지될 것이다.

위의 체계를 사용하는 주요 문제는 CPU가 느린 CPU보다 훨씬 빨리 계산된다는 것이다.또한, 고급 컴퓨터 시스템은 계산을 용이하게 하는 정교한 파이프라인과 다른 유리한 특징들을 가지고 있다.결과적으로, 최첨단 시스템을 사용하는 스팸 발송자는 그러한 억제의 영향을 거의 받지 않을 것이고, 보통 시스템을 사용하는 일반 사용자들은 부정적인 영향을 받을 것이다.새로운 PC에서 몇 초가 걸리는 연산이라면, 오래된 PC에서는 1분, PDA에서는 몇 분 정도 걸릴 수 있는데, 이것은 오래된 PC 사용자들에게는 귀찮은 일이 될 수 있지만 PDA 사용자들에게는 아마도 받아들일 수 없을 것이다.클라이언트 CPU 속도의 차이는 CPU 바인딩된 기능에 기초한 모든 계획의 광범위한 채택을 가로막는 중요한 장애물 중 하나이다.따라서 연구자들은 대부분의 컴퓨터 시스템이 거의 동일한 속도로 평가할 기능을 찾는 것에 관심을 가지고 있다. 따라서 고급 시스템은 CPU 격차가 암시할 수 있는 것처럼 로우엔드 시스템보다 (2~10배는 빠르지만 10~100배는 빠르지 않음) 이러한 기능을 다소 빠르게 평가할 수 있다.이러한 비율은 의도된 용도에 충분히 "평등한" 것이다. 즉, 함수는 남용 억제에 효과적이며 광범위한 시스템에 걸쳐 합법적인 상호작용을 엄청나게 지연시키지 않는다.

새로운 평등주의적 접근법은 기억력에 의존하는 것이다.앞에서 설명한 것처럼 메모리 바인딩 함수는 계산 시간이 메모리에 접근하는 데 걸리는 시간에 의해 지배되는 함수다.메모리 바인딩 함수는 캐시를 사용하는 것이 효과적이지 않은 방법으로 예측 불가능한 방법으로 메모리의 넓은 영역에 있는 위치에 접근한다.최근 몇 년 동안 CPU의 속도는 급격히 증가했지만, 보다 빠른 메인 메모리를 개발하는 데는 비교적 작은 진전이 있었다.최근 5년간 구축된 기계의 메모리 지연 비율은 일반적으로 2보다 크지 않으며 거의 항상 4보다 작기 때문에 메모리 바인딩 기능은 가까운 미래에 대부분의 시스템에 대해 평등할 것이다.

참고 항목

참조

  1. ^ Dwork, Cynthia; Naor, Moni (1992). "Pricing via Processing or Combatting Junk Mail". Advances in Cryptology – CRYPTO 1992, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16-20, 1992, Proceedings: 139–147. doi:10.1007/3-540-48071-4_10. (동일 버전 변경)

외부 링크