DevMemo

네트워크 흐름 문제(Network Flow Problem)은 일종의 그래프를 응용한 문제입니다. Programming Challenge를 풀다가 이해가 가지 않아 찾아 보았습니다. Programming Challenge 번역판의 설명은 원서가 이상한 건지 번역이 이상한건지 읽어도 읽어도 뜻을 이해할 수 없었습니다. 혹(?) Programming Challenge 번역판의 설명만으로 모든게 다 이해되는 분...? 공감? 네트워크 흐름 문제에서 가장 중요한 것은 가중치 그래프에서 간선(Edge)의 값의 의미를 이해하는 것입니다. 일반적인 가중치 그래프 문제에서 간선(Edge)은 해당 간선을 이동하기 위한 소요 비용으로 간선의 가중치 전체를 사용합니다. 하지만 네트워크 흐름 문제에서 가중치는 허용 가능한 크기..

The Dynamic Database Class Based on ATL/OLE DB 현재 참조하고 있는 코드프로젝트 글입니다. OLEDB 관련된 ATL클래스를 사용하기 쉽게 만들어 놓았습니다. 물론 MFC에서 바로 사용할 수 있겠죠. 물론 라이브러리 사용하려면 기초적인 ATL과 OLEDB구조는 알고 있어야 합니다. 사실 OLEDB는 ATL형식으로 되어 있어 복잡하다고 느껴지는게 사실입니다. 그러나 막상 이해하고 나면 또 별것도 없는게 OLEDB가 아닌가 합니다. 2002년 글로서 아직까지도 지존 중에 한개인걸로 보아 검증받은 코드라는 생각이 듭니다. ODBC와 ADO보다 강력한 DB라이브러리를 원하시면 볼만 합니다. 이 코드는 동적인 관계로 ATL마법사로 만드는 정적인 클래스 기반의 DB처리보다 속도는 ..

Four Ways to Use the Concurrency Runtime in Your C++ Projects 2009년 10월의 msdn매거진에 나온 병렬 런타임을 사용하는 예제입니다. User Interface의 반응성을 높이기 위하여 배경쓰레드를 사용하는 전통적인 방법을 PPL의 agent를 활용하였을 떄 얼마나 코딩이 더 쉬워지고, 더 굳건해지는 지를 보여주고 있습니다. 참고로 Agent는 병렬처리 엔진에 의한 별도의 쓰레드에서 작동하며 메시지로 데이터를 주고 받습니다. 병렬처리용인 관계로 CPU 개수나 코어 개수에 따라 물리적으로는 별도의 CPU에서 작동할 것입니다. 다른 말로 바꾸면 싱글CPU에서는 오히려 오버헤드가 걸린다는 이야기가 됩니다. 개인적인 지식과 경험으로 보았을 때는 IOCP같은 ..

Parallel Patterns Library (PPL)은 Visual Studio 2010에 포함될 예정인 Microsoft의 템플릿 기반 멀티프로세스 프로그래밍 라이브러리 입니다. 라이브러리는 MS독자적인 모델로 인텔의 쓰레딩빌딩블록과 유사한 형태를 가지고 있으며 전반적인 인터페이스 모양은 쓰레딩빌딩블록처럼 STL의 모습을 따릅니다. VS2010의 병렬런타임(Concurrency Runtime)은 협업적 태스크 스케줄링(Cooperative Task Scheduling)과 협업적 블록킹(Cooperative Blocking)에서 강점을 가지고 있습니다. 개념적으로 보자면 협업적 태스크 스케줄링이라는 것은 태스크가 끝난 쓰레드에 자동으로 사용 가능한 다른 태스크를 할당하는 등의 효과적인 스케줄링을 의미..

주기적인 두 이벤트가 동시에 일어나는 주기 구하기 -> 최소공배수 올해 생일의 요일을 알고 있을때 내년 생일의 요일을 구하기 -> 365/7의 나머지를 요일에 더해주면 된다. RSA 알고리즘 -> 메시지를 어떤 정수 m으로 코딩한 다음 k승을 구하는데, k가 공개 키또는 암호화 키이다. 그리고 결과를 n으로 나눈 나머지를 구한다. m,n,k는 모두 매우 큰 정수이다. 결과적으로 m^k mod n을 모듈러 계산을 활용하여 효율적으로 구해야 한다.

Intel's Threading Building Block은 멀티프로세서 프로그래밍을 지원하는 인텔의 C++ 템플릿 라이브러리로 멀티플랫폼을 지원합니다. 이 라이브러리는 Epic Games Unreal Engine3 에 포함되어 있습니다. 자세한 것은 정식 홈페이지를 참고하여 주세요. MPP에 대한 대부분의 것이 그러하듯 라이브러리 사용법은 그리 어렵지 않으나 배경지식으로 요구하는 것이 꽤 있고 난이도가 좀 있습니다. 뭐랄까 개인적으로는 멀티쓰레드 프로그래밍이 OS에 대한 개념을 많이 요구하는데 비하여 멀티프로세서 프로그래밍은 CPU, Cache, Memory와 같은 H/W 동작 앨고리듬에 대한 지식과 병렬처리에 대한 개념을 요구합니다. 제가 읽은 것은 Tutorial로 집중력과 끈기를 요하며 시간이 좀..

이틀에 걸쳐 읽은 글은 Memory Consistency Models 라는 글입니다. 멀티프로세서 관련 프로그래밍을 요새 주의 깊게 보고 있는데 정말로 배경으로 요구하는 지식이 64bit 프로그래밍과는 수준을 달리하는 것 같습니다. 이 글은 배경지식이 되는 글로 메모리의 동기화 모델에 대하여 나와 있습니다. 멀티CPU에서의 동기화는 싱글CPU와는 다른 캐쉬간의 동기화 문제가 발생하는 관계로 이런 글은 참고로 읽어둘 필요가 있습니다. 참고로 이 글은 분산처리에서의 공유메모리에 대해서도 언급하고 있습니다. 간단히 요약하면 아래와 같으며 흥미를 느끼신다면 원문을 찾아 읽으시길 바랍니다. 원문에는 Shared Memory Consistency Models: A Tutorial을 읽어볼 것을 추천하고 있습니다. ..

Message Passing Interface(MPI)란? OpenMP와 함께 병렬처리 프로그래밍의 표준의 한축을 담당하고 있는 Message Passing Interface는 슈퍼컴퓨터에서 나온 개념 입니다. CPU가 공유메모리가 아닌 직접적인 통신을 할 때 사용하는 메시지 기반 API로 90년대 초반 벤더별 API가 개발되기 시작하여, 표준API 초안이 1994년 12월에 나왔습니다. OpenMP가 병렬 태스크 범위와 범위에 따른 처리 CPU 개수들을 지정하는데 비하여 MPI는 개별 CPU를 제어합니다. MPI API의 주요 목적은 공유메모리가 아닌 CPU간 직접 메시지 통신이지만 이 통신을 통하여 Master-Slave구조가 이루어져 Master CPU에서 보낸 메시지에 따라 Slave CPU들이 ..

OpenMP란 멀티쓰레드 기법을 이용하여 병렬처리를 간단히 구현하는 API입니다. C/C++ 그리고 Fortran을 지원하며 C/C++에서는 compiler directives, 라이브러리 루틴, 환경 변수로 이루어지며 실제 사용은 compiler directives로 간단히 할 수 있습니다. 내부적으로는 master쓰레드가 CPU 코어 개수만큼 쓰레드를 생성하여 특정 블럭 내의 내용을 각각의 코어가 병렬적으로 처리할 수 있게 할당하여 처리합니다. 병렬처리 자체는 루프 내의 내용 나누기, 특정 코드내의 섹션 나누기로 크게 나누어 집니다. 하루정도 간단히 사용한 경험으로는 간단한 컴파일 디렉티브 만을 가지고 하나의 함수 내의 처리를 CPU 코어 개수만큼 병렬로 가져가 성능 향상을 이룬다는 것이 굉장히 유용..

이 글은 Wikipeida의 Non-Uniform Memory Access를 요약하여 놓은 것입니다. Non-Uniform Memory Access or Non-Uniform Memory Architecture (NUMA)는 멀티프로세서에 사용되는 개념으로 각각의 프로세서는 자신의 로컬메모리를 가지게 되어 자신의 로컬메모리에 대한 처리가 굉장히 빠른 아키텍처를 말합니다. 이는 Symmetric Multi Processing(SMP, 멀티프로세서가 같은 메모리를 공유하는 일반적인 방식)에서 확장 되었으며 1990연대에 Unix계열의 H/W에서 채용되었습니다. Basic Concept 처음에는 메모리의 속도가 CPU의 속도보다 빨랐으나 기술 진보에 따라 이 현상의 역전되었다. CPU는 느린메모리 속도를 고속..

이글은 zdnet에 동영상 강의를 저의 편의성에 맞게 요약하여 놓은 글입니다. 강의자는 James Reiners (Director, Intel Corporation)으로 MPP에 등장 배경에서 부터 개념, 라이브러리 소개등을 하고 있습니다. Modern CPU Design Power Consumption -> 성능을 높이기 위하여 더 높은 전력을 요구하는데 비하여 더 적은 전력량으로 n개의 CPU를 돌릴 경우 더 높은 성능을 얻을 수 있다. 즉, 클락을 줄이는 대신에 남는 전력으로 n개의 CPU를 돌리는 것이다. i.e. overclock으로 13%의 성능 향상을 얻기 위하여 73%의 전력을 더 사용하여야 함 최근에는 전력을 더 사용해도 큰 성능 향상을 얻을 수 없음 반대로 전력을 덜 사용하고 n개의 C..

이 책은 미국 유명 SW회사 면접을 준비하기 위한 책인 듯 보인다. 내용적으로 크게 두가지로 나누어져 있다고 볼 수 있다. 한부분은 구직활동, 이력서 작성, 면접 등의 과정에 대한 서술과 다양한 팁이다. 그리고 다른 반쪽인 본론인 다양한 면접 문제의 종류와 샘플 그리고 풀이법으로 이루어져 있다. 이 책의 번역 수준은 좋으나 언어적 체계가 우리와 달라 풀이법이 언어적으로 한눈에 들어오지는 않는다. 또한 425 페이지 밖에 안되는 짧은 책이지만 수학적 혹은 논리적인 사고를 많이 요구하는 관계로 수학책을 읽는 것 만큼이나 진도는 천천히 나간다. 그럼에도 불구하고 이 책은 읽을 가치가 있는 책이다. 읽으면서 저자들에 대하여 생각하는 프로그래머들 같다라는 것이 느껴지기 때문이다. 면접 문제지만 현업을 하다보면 마..

암달의 법칙(Amdahl's Law) 연산의 p비율만큼만 병렬화가 가능한 경우, 최대 속도 향상은 1/(1-p) Work Law T1: 1개의 프로세스 사용시 최단 수행 시간 TP: P개의 프로세스 사용시 최단 수행 시간 TP >= T1/P Span Law 병렬실행시 반드시 실행해야 하는 최단 길이, 즉 임계 경로로 1개의 프로세스로 실행시 가장 빠른 실행 시간을 나타냄 Parallelism T1: 모든 노드의 수행시간 T@: 무한개의 프로세스 사용시 최장 패스 노드 수(수행 시간) T1(=최단길이)/T@(=프로세스 개수): 무한개의 프로세스 사용시의 최대 속도 향상 i.e. 18(총 노드 개수) / 9(최장 패스 노드)

64-Bit Programming Models: Why LP64? Open Systems community에서 왜 LP64모델을 Unix표준으로 선택하였는가에 대한 요약입니다. LP64모델을 선택하기 위하여 포팅성(Portability), 32bit 환경과의 상호운용성(Interoperability with 32bit Enviroments), 표준 준수(standards conformance), 성능(performance effects), 전이비용(transition costs)을 고려하였습니다. 64bit모델을 고려하기 시작한 것은 H/W발전에 따라 4G이상의 주소에 직접적으로 억세스하려고 하는 것을 필요로 해졌기 떄문입니다. 기존의 64bit 환경에 대한 경험상 해당 환경의 개발자들은 32bit 프로..