Rommance - Daniel Jiseok Song

"This is one reason that ASICs have significantly lower power than processors. They generally minimize the use of large centralized memories, and prefer local registers or recomputation. Further, these local registers provide direct communication in a pipelined stream-like fashion between compute entities and avoid the use of shared memories to pass values."

공유된 메모리가 에너지 소모를 크게 한다는 이야기입니다. ASIC이 전력소모가 적은 이유가 공유 메모리를 쓰기 보다는 재계산이나 통신(파이프라인에 직접)을 통해 전달하기 때문입니다.

Embedded Systems Design에서 기사를 본 거였는데, 발표자료를 찾아보니 같은 내용이 있기에 보니까 저자가 같네요. 2007년 기사입니다.

 

Communication Cheaper than Memory Access, Anant Agarwal

위의 표를 보면 차라리 네트웍으로 보내는 것이 캐시나 메모리를 통하는 것 보다 훨씬 적게 에너지가 소모됩니다. 되도록 공유 메모리를 적게 쓰는 것이 좋겠네요. 그리고 메모리 자체도 작게 (footprint)

그래서 말인데,

왜 ASIC으로 하면 전력소모가 적은데 그걸 embedded processor를 써서 만들면 에너지 소모가 클 수밖에 없을까요?

같은 일을 해도 OS 올라가고 메모리 붙이고 하면 에너지 소모가 크게 됩니다. 또 multicore라도 shared memory model은 어쩔수 없나봅니다. 에너지 소모가 ASIC보단 많게되겠네요

어쩌면 SW 패러다임이 바뀌어야할 것 같습니다. 멀티코어가 1K ,10K쯤 되면 코어들은 일종의 look-up table이 될 거라고 하던데 그럴 때는 메모리 공유보다는 네트웍 모델이나 stream 모델이 맞을 것 같습니다. 그런 이름이 있는지는 모르지만. streamC라는 게 있던데.. 좀 된 자료입니다. 2002년. http://graphics.stanford.edu/streamlang/ 구글에서 stream processor를 찾아보면 많이 나오는군요. 이건 어떻게 봐야되나

http://www.embedded.com/products/integratedcircuits/173400008?_requestid=405592 여길 나중에 좀 읽어봐야겠습니다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

http://www.springerlink.com/content/n4u12093t15m8913/

http://dspace.mit.edu/bitstream/1721.1/35612/1/75293670.pdf

James  Ryan Psota 2005 thesis(MS) MIT

rMPI: Message Passing on Multicore Processors with On-Chip Interconnect

With multicore processors becoming the standard architecture, programmers are faced with the challenge of developing applications that capitalize on multicore’s advantages. This paper presents rMPI, which leverages the on-chip networks of multicore processors to build a powerful abstraction with which many programmers are familiar: the MPI programming interface. To our knowledge, rMPI is the first MPI implementation for multicore processors that have on-chip networks. This study uses the MIT Raw processor as an experimentation and validation vehicle, although the findings presented are applicable to multicore processors with on-chip networks in general. ...

MPI를 사용한 CMP용 rMPI.

MPI가 오버헤드가 크긴 하다. Shared memory(pthread)를 쓰는 경우보다.

첫번째 on chip MPI라서 의미가 있다고 한다.

 

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

프로그램에서 배열로 쓰는 것 보다는 구조체나 클래스를 정의해서 쓰는 게 알고리즘적으로는 더 스마트합니다.

그런데 하드웨어 입장에서 보면 캐쉬 구조상 관련된 것들끼리 메모리상으로 가까울 것으로 예상하고 또한 성능이 더 좋습니다.

그렇다면 구조체나 클래스를 쓸 때도 캐쉬를 생각해서 구조를 잡는 게 유리하겠죠

 

그에 대한 페이퍼를 찾아봤는데

scholar.google.com에서

class struct cache live

이렇게 검색하니 나오네요.

ftp://ftp.cs.wisc.edu/wwt/pldi99_cache_def.pdf 99년에 나온 페이퍼입니다. 아직 읽어보진 않았습니다.

Trishul M. Chilimbi, Bob Davidson, James R. Larus

A program’s cache performance can be improved by changing the
organization and layout of its data—even complex, pointer-based
data structures. Previous techniques improved the cache performance
of these structures by arranging distinct instances to increase
reference locality. These techniques produced significant performance
improvements, but worked best for small structures that
could be packed into a cache block.

후략

같은 사람이 2000년에 낸 페이퍼도 있습니다.

http://ftp.cs.wisc.edu/wwt/computer00_conscious_original.pdf

Trishul M. Chilimbi, Mark D. Hill, James R. Larus

Making Pointer-Based Data Structures Cache Conscious

위스콘신대랑 MicroSoft

 

http://www.info.uni-karlsruhe.de/lehre/2002SS/uebau2/papers/ChilimbiHillLarus-1999.pdf

Proceedings of the SIGPLAN ‘99 Conference on Programming Languages Design and Implementation (PLDI 99), May 1999,
Atlanta Georgia.

Trishul M. Chilimbi, Mark D. Hill, James R. Larus

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

http://perfmon2.sourceforge.net/ols2006-perfmon2.pdf

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

 

PinOS: A Programmable Framework for Whole-System Dynamic Instrumentation

 

http://www.eecs.harvard.edu/~prash/pape ··· aper.pdf

 

PinOS is an extension of the Pin dynamic instrumentation framework for whole-system instrumentation, i.e., to instrument both kernel and user-level code. It achieves this by interposing between the subject system and hardware using virtualization techniques. Specifically, PinOS is built on top of the Xen virtual machine monitor with Intel VT technology to allow instrumentation of unmodified OSes.

 

PinOS is based on software dynamic translation and hence can perform pervasive fine-grain instrumentation. By inheriting the powerful instrumentation API from Pin, plus introducing some new API for system-level instrumentation, PinOS can be used to write system-wide instrumentation tools for tasks like program analysis and architectural studies. As of today, PinOS can boot Linux on IA-32 in uniprocessor mode, and can instrument complex applications such as database and web servers.

 

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

A Hardware/Software Framework for supporting Transactional Memory in a MPSoC Environment

Cesare Ferri	Brown University, Providence, RI
Tali Moreshet	Swarthmore College, Swarthmore, PA
R. Iris Bahar	Brown University, Providence, RI
Luca Benini	University of Bologna, Bologna, Italy
Maurice Herlihy	Brown University, Providence, RI

http://portal.acm.org/citation.cfm?id=1 ··· fulltext

멀티코어로 가는 대세 - 더이상 클럭을 올려서는 힘들고 여러개 코어로 나눠 일하는 concurrency 를 공략하는게 대세다
참고로 2003년 이후로는 거의 클럭이 올라가지 않고 있다.
클럭을 올려 속도를 빨리 하는 대신에 여러 코어에서 나눠 돌려서 전체적인 처리작업량을 늘리는 방법을 쓴다.
이렇게 하면 에너지(열)은 클럭주파수의 제곱에 비례하므로 낮은 클럭의 칩을 여러개 써서 높은 클럭 칩 하나로 일하는 것과 같은 성능을 낸다면 대체로 에너지를 더 적게 소모하고 열이 더 적게 나게 된다.
그러나 여러 코어에서 돌리려하면 일을 나누는 것, 그리고 나눠서 잘 돌아가게 관리해주는 게 필요하다.

예를 들어서 피자 집에서 배달을 시키는데 원래 한명이 배달하다가 손님이 많아져서 두명으로 늘렸다고 치자.
아무리 둘로 늘려도 효울이 두배로 늘려면 당연히 피자가 나오는 속도가 두배여야 한다.
그리고 혹, 오토바이나 피자 배달을 준비하기 위한 데크등이 공용된다면 공용되는 자원을 누가 먼저 사용하는지 규칙이 있어야 하고 한번에 한사람만 쓰도록 관리해줘야 한다.

원래 기존에 컴퓨터과학에서 많이 쓰던게 락(잠금)기법인데
잠가버려서 한번에 하나만 쓰게 보장된다.
그러나 혹시 락을 건 상태로 프로세스가 죽거나 잠들어버리면 다른 기다리는 프로세스들은 하염없이 기다리게 된다.
기타 여러 문제가 있는데 이걸 해결해보고자 transactional memory가 나왔었다.
최근에 멀티코어가 많이 나오면서 다시 재조명 받게 된 주제인데

컨셉은
  일단 해본다.
  그리고 잘 안되면 기다렸다 다시 한다.
이다.

그러니까 공유자원 A가 있다면
모든 각각의 프로세스에서
기본적으로 다른프로세스가 내가 자료 A를 처리하는 동안에 A를 바꾸지 않았다는 가정하에
일단 계산을 해본다.
프로세스1이 그랬다고 치고
그리고 A값을 아마 업데이트 할텐데
그 전에 혹시 다른 프로세스가 A를 바꿨다면 이 프로세스1은 바꿨다는 것을 인식하게 된다.(인식하는 방법은 이 논문에 나온 방법은 하드웨어적으로 Cache Coherency를 이용한다.)
이때 Abort가 발생한다.
그러면 자기가 했던 작업들을 다 취소하고 새로 시작한다.

락 Lock은 기본적으로 비관적으로 남이 반드시 내 자원을 침범할 것이라 보고 미리 자물쇠를 걸어두는데
TM(Transactional Memory)은 낙관적으로 내 자원이 남에게 침범받지 않았을 거라고 가정하고 일단 해보는 것이다.

첨부한 프리젠테이션자료에 나오는 그래프처럼 어떤 상황에서는 일반적인 Lock이 프로세서가 늘어나면 각 프로세서에서 소모하는 시간이 기하급수적으로 늘어나는데 비해
TM은 상당히 괜찮다.

Review한 이 논문은  이 TM을 임베디드 환경에 맞춰서 간단한 TM을 가진 프로세서를 설계해 시뮬레이션해보고 어땠는지 보는 것이다.
결론은
 "성능은 좋아진다.
 그러나 Critical Section(프로그램에서 공유자원 사용하는 부분)에서 하는 일이 적을 경우 오히려 TM 기능을 구현하기 위한 하드웨어의 전력 소모때문에
 전력은 일에 따라 TM쪽이 더 많이 소모되기도 한다.
 그래서 TM을 임베디드에 적용하려고 해도 너무 간단하게는 말고 좀더 설계에 신경써야 된다."
이다.
TM 자체를 처음 접하는 거라 공부삼아 리뷰했다. Cite된 논문들 읽는 것 벅찼다. 처음 보는 게 너무 많아서..
결국 교수님께 모르는 부분 집혀서 곤란도 당했다.

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

http://asmlove.co.kr/zBdC7/download.php?id=280
(원문이 자세함.)
1. Fully Associative Cache Schematics
Fully Associative 캐시는 Cache Set으로 캐시를 나누지 않고 태그 정보로만 데이터를 찾는다.
단순하게 복잡도를 계산해보면 최악의 경우 2^T 번의 태그 비교가 필요해지므로 O(2^T)의 계산 복잡도를 가진다.
T비트의 비교기는 동작 속도가 매우 빠르지만 캐시 메모리가 커질수록 태그 값을 찾는데 긴 시간이 필요하다는 단점이 있다. 하지만 데이터의 주소를 그대로 캐시 메모리에 저장하므로 유연성이 높다는 장점도 있다.

2. Direct-Mapped Cache Schematics
Fully-Associative 방식을 보완한 것이 Direct-Mapped 방식이다. 메모리 주소를 태그, 셋, 오프셋으로 나누고, 캐시 메모리도 셋 단위로 나눠서 관리한다. 셋 번호에 따라 어느 캐시 라인에 데이터가 있는지 먼저 찾고, 그 안에서 태그 값을 비교해서 원하는 캐시 데이터가 맞는지 확인하는 방식이다.
캐시 라인의 번호가 Cache Set의 번호가 된다. 따라서 셋 번호를 검색하는 시간이 줄어들고 태그 번호만 비교하면 된다. Fully Associative 방식에 비해 동작 속도가 매우 빨라진다.
제작 비용이 싸지는 장점이 있지만 동일한 셋 번호를 가지는 메모리 주소를 함께 저장할 수 없다는 단점이 있다. 따라서 연속된 메모리 데이터를 캐시에 저장할 수 없게 되고, 캐시의 성능이 떨어지게 된다. 예를 들어 0x16339C와 0x16338C는 같은 셋 번호를 가지므로 같은 캐시 라인에 들어가게 된다. 따라서 캐시에는 둘 중 하나의 데이터만이 저장되고 두 데이터가 동시에 저장될 수 없다. 가까운 메모리가 함께 사용된다는 Locality를 생각해보면 매우 성능상에 문제를 가져올 수 있다.

3. Set-Associative Cache Schematics
Set-Associative 방식은 위의 두가지 방식의 장점들을 합쳐서 만든 방법이다. 캐시를 태그로만 나누는 것이 아니라 같은 셋 값으로도 나누어서 태그 값이 같지만 셋 값이 다른 데이터들도 캐시에 저장될 수 있도록 한다.
n-Way Set-Associative 라는 말은 그림과 같이 태그가 같은 데이터 라인이 n개까지 있을 수 있다는 말이다. 즉, 태그가 다르고 셋 값이 같은 데이터 라인이 몇 개가 캐시에 있을 수 있는지를 나타내는 말이다.
여기에서 n 값이 너무 높아지면 Fully Associative 방식의 단점이 나타나고, n 값이 너무 작아지면 Direct Mapped 방식의 문제가 나타나므로 Trade Off에 대한 고려가 필요해진다.

EzDoum 사이트: [Cache] 2-way Set-Associative 방식이란 무엇일까?
http://www.ezdoum.com/stories.php?story ··· F5962073
What every programmer should know about memory
http://people.redhat.com/drepper/cpumemory.pdf

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.

연구실에서 국가지정 과제의 일환으로 기술정보를 제공하고 있습니다. 교수님이 찾으셔서 올리시는 자료들은 쓸만한 게 많은 것 같습니다.
 
Google Fellows Reveal Parallel Processing Model

아마 한글 번역판 뉴스가 나올 법한데..
"MapReduce: Simplified Data Processing on Large Clusters," 라는 논문을 발표했답니다.

구글은 직접 만들거나 싸게 살 수 있는 PC급의 시스템들을 엄청나게 클러스터링해서 자기들 시스템으로 이용하는 것으로 유명합니다. 예를 들어 10만대를 쓴다면 중간에 유지보수를 위해 꺼지는 컴퓨터도 있을 것이고 고장나거나 네트웍 이상으로 잠시 접근이 불가능해지는 노드들이 있을 겁니다.
이런 환경에서 안정적인 서비스를 어떻게 지원하는지가 구글의 노하우이고 또한 거기에 관련된 논문도 많이 발표하는 걸로 알고있습니다. 대학에 그와 관련된 이슈로 지원도 많이 하구요.

The method, known as MapReduce, lets users break computations into a map and a reduce function, which the runtime system automatically parallelizes across large clusters while navigating machine failures and honing the efficiency of network and disk use in the process.

이 MapReduce 라는 방법을 통해 사용자가 처리할 작업들을 실행중에 병렬화하고 클러스터들에 나눠준다고 합니다. 기계 고장이나 네트웍 사용량, 디스크 사용량을 "검색"하면서 적절하게 말이죠.
Fault tolerance와 병렬 처리, 데이터 분산, 로드 밸런싱등이 라이브러리를 통해 추상화 됩니다. 이런걸 라이브러리만 쓰면 해결되게 했다니 대단합니다.

From : ACM TechNews; Friday, January 11, 2008

크리에이티브 커먼즈 라이센스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이센스에 따라 이용하실 수 있습니다.