20150324

1. 영어 기사 읽기
1) Teotihuacán’s Social Tensions Contributed to Its Fall, Scientific American
2) The eternity drive: Why DNA could be the future of data storage, CNN
– While this census has only been running five years, the statistics show a 22% attrition rate over four years. (attrition – 소모)


2. Computer Architecture 청강
– Prefetching 관련 논문을 추천해주심. 읽지 않은 것을 읽어보기.
-> [ASPLOS’92] Design and Evaluation of a Compiler Algorithm for Prefetching
-> [HPCA’03] Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-order Processors
– 만약에 ideal한 prefetcher가 있다면 cache가 없어도 된다. Cache는 미래에 필요한 데이터이긴 한데 prefetcher가 가져오지 못하는 것을 담아두기 위한 일종의 버퍼이다. 따라서 ideal한 prefetcher가 있다면 cache는 없어도 된다.
– Prefetcher의 misprediction은 correctness에 영향을 주지 않는다. 필요없는 것을 가져오는 경우, 사용하지 않으면 되기 때문이다. 상태를 복구시켜줄 필요가 없다. 반면에 branch misprediction, value misprediction은 복구가 필요하다.

Prefetching: The four questions

1) What address to prefetch
– 불필요한 prefetch는 memory bandwidth, cache, energy의 낭비 유발함
– 무엇을 prefetch할지 결정하는 방법 : 데이터 접근 패턴을 보거나, 컴파일러의 힌트 사용

2) When to initiate a prefetch request (timeliness)
– Prefetch를 너무 일찍하면 evict되며, 너무 늦게하면 latency를 숨기지 못함.
– 너무 늦게 prefetch request를 보내면 그 데이터를 사용하지 못할 수 있음.

3) Where to place the prefetched data
A. Prefetch data를 넣는 HW : (Cache / Prefetch buffer)
– Prefetch data를 캐시에 넣으면 구현이 복잡해지지 않고, 추가 hardware가 없어도 된다.
– Prefetch data를 prefetch buffer에 넣으면 캐시 오염이 발생하지 않으나, 메모리 시스템 설계가 훨씬 복잡해진다. Coherence request가 cache와 prefetch buffer 모두에 가야 하고, 캐시 접근할 때에도 모두에 접근해야 한다.
B. 어느 캐시에 대해 prefetch할 것인가? (L1 / L2)
– Prefetcher가 정확하며 적정 시점에 데이터를 넣어줄 수 있다면 L1에 prefetch하는 것이 최선이다. 하지만 부정확할 경우 L1에 prefetch하는 것은 오버헤드를 증가시킨다. 실제로는 정확도를 위해 L1, L2에 각각 다른 prefetcher를 설치함.
C. prefetch한 데이터를 캐시의 어느 위치에 넣을 것인가?
LRU / MRU. 원래 접근한 데이터는 MRU position에 insert하고 LRU position을 evict한다. 하지만 prefetch data는 demand된 data가 아니므로, LRU position이나 가운데 넣을 수도 있다.
D. Prefetcher를 memory hierarchy에서 어디에 위치시킬 것인가?
Prefetcher를 어떻게 학습시킬 것인가를 결정하는 것이다. Core와 L1 사이에 둔다면 코어의 메모리 접근 패턴을 볼 수 있지만, L1과 L2 사이에 둔다면 코어의 메모리 접근 패턴을 볼 수 없다. Accuracy를 높이기 위해서는 memory hierarchy에서 높은 위치에 prefetcher를 넣는 것이 좋다. 하지만 그런 경우 memory bandwidth 소모가 매우 늘어남. 한편 memory hierarchy에서 높은 곳에 prefetcher를 둔다면, memory로 가는 request를 막는 역할을 하지 못함.

4) How to prefetch
– Software prefetching
ISA가 제공하는 prefetch instruction 사용해 prefetch한다. Programmer 또는 컴파일러가 prefetch 명령을 바이너리 중간에 삽입한다. 규칙적인 메모리 접근의 경우에 효율적이다. Page coloring도 SW prefetch의 한 가지 방식이다. 전체 캐시가 8MB가 있어도, 2MB만 쓰도록 SW적으로 하는 것이 page coloring 기법.
Software prefetching은 architectural aspect를 반영하지 못하고, static하게 분석해야 하므로 regular pattern을 찾아내지 못할 가능성이 높다. 만약 compiler가 모든 load instruction 앞에 prefetch instruction을 삽입한다고 하자. 그렇게 되면 BW 소모가 너무 크다. 이 경우에 IPC는 높게 나올 것이지만 실제로는 무의미한 prefetch instruction이 많게 된다. 일반 프로그래머는 잘 쓰지 않지만, 라이브러리를 제작하는 개발자는 자주 사용함.
-> Prefetching의 두 가지 방식 ( Binding / Non-Binding )
Binding 방식의 prefetch는 prefetch한 데이터를 캐시가 아니라 레지스터에 넣는 것. Prefetch instruction이 따로 구현되어있지 않은 경우에 이렇게 prefetch를 구현한다. Prefetch하기 위해서 load 명령을 사용한다. 하지만 이 경우 parallel thread programming에서 consistency가 유지되지 않을 수 있다. Non-binding 방식의 prefetch는 prefetch한 데이터를 cache에 넣는 것.
– Hardware prefetching
Load/store access 패턴을 탐지해 미래에 필요한 것을 가져온다. Architectural aspect를 잘 반영하며, code compatibility issue 없음. Next-line prefetcher는 매우 단순. 바로 다음 캐시라인을 가져오는 것. 일반적으로 잘 동작하며, 불규칙적인 패턴에는 BW 소모한다는 단점이 있음. 반대 방향으로 진행하는 경우에 문제가 될 수 있음. (previous 접근) Stride prefetcher는 stride를 파악해 이를 가져오는 것. 동일한 비용을 가정할 때, feedback directed prefetcher가 가장 잘 동작한다.
– Execution-based prefetchers

궁금한 것
– 그렇다면 core와 L1 miss의 메모리 접근 패턴을 동시에 보는 prefetcher를 쓰면 어떤가?

– Instruction based prefetch의 경우, program counter를 사용해 인덱싱하는데, context prefetching이 발생해도 여전히 유효한지 궁금함. 교수님께 여쭤보니, 그것은 신경쓰지 않아도 된다고 하심. Prefetcher는 빠르게 학습하기 때문이다. Context switching이 발생하면 초반에는 prefetcher가 제대로 작동하지 않겠지만, 그 이후로는 제대로 작동할 것이다. Prefetcher는 어플리케이션의 한 time slice에서 작동하는 것을 기대하고 추가하는 것이다. 따라서 문제가 없다.

– Prefetch한 데이터를 가져올 수 있는 위치에 두 가지가 있다. Cache에 넣을 수도 있고 prefetch buffer에 넣을 수도 있다. Prefetch buffer를 사용하지 않는 이유는 무엇일까? Cache에 prefetch data를 가져왔을 때, 그것으로 인한 cache pollution에 의한 영향보다 large size로 인한 장점이 크기 때문인가?


3. 여러 프로그램의 실행 시점 맞추기
여러 개의 워크로드가 실행될 때, 이들의 실행 시점을 맞출 필요가 생김. 대강의 개념은 알지만, 구체적으로 어떻게 할지 몰라 고민. 생각해보니, 저번에 정섭이 형으로부터 소스 코드를 받은 적이 있었음. 이 코드는 [1]에서의 코드와 거의 같다.

set_semaphore.cpp

#include <iostream>
#include <fcntl.h>
#include <unistd.h>
#include <stdlib.h>

#include "sem_helper.h"
#include "ptlcalls.h"

using namespace std;

int main (int argc, char** argv)
{
	int sem_id;
	int sem_val;
	int rc;

	if (argc < 3) {
		cout << "Usage: " << argv[0] << " [semaphore value] [checkpoint name]" << endl;
		return 1;
	}

	/* Get semaphore */
	sem_id = get_semaphore();

	/* Retrive semaphore value from command line arg */
	sem_val = atoi(argv[1]);

	/* Set semaphore value */
	rc = set_semaphore(sem_id, sem_val);
	if (rc == -1) {
		perror("set_semaphore: semctl");
		return 1;
	}

	/* Now wait for semaphore to reach to 0 */
	wait_semaphore (sem_id);

	/* All threads will be in ROI so either create a checkpoint or
	 * switch to simulation mode. */
	ptlcall_checkpoint_and_shutdown(argv[2]);

	return 0;
}

sem_helper.h

/* This file provides basic function to synchronize multiple processes using
 * System V Semaphores.  It uses semaphore id 786 so please make sure none of
 * your benchmarks uses that ID. */

#ifndef SEM_HELPER_H
#define SEM_HELPER_H

#include <errno.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

static int SEM_ID = 786;

int get_semaphore ()
{
	int sem_id;

	sem_id = semget(SEM_ID, 1, IPC_CREAT | 0666);

	if (sem_id == -1) {
		perror("get_semaphore: semget");
		exit(1);
	}

	return sem_id;
}

int set_semaphore (int sem_id, int val)
{
	return semctl(sem_id, 0, SETVAL, val);
}

void decrement_semaphore (int sem_id)
{
	struct sembuf sem_op;

	sem_op.sem_num  = 0;
	sem_op.sem_op   = -1;
	sem_op.sem_flg = 0;

	semop(sem_id, &sem_op, 1);
}

void wait_semaphore (int sem_id)
{
	struct sembuf sem_op;

	sem_op.sem_num  = 0;
	sem_op.sem_op   = 0;
	sem_op.sem_flg = 0;

	semop(sem_id, &sem_op, 1);
}

#endif

아래는 코드에서 쓰이는 세마포어 관련 라이브러리 함수에 대한 설명이다 [5, 6, 7].

semget() 함수는 세마포어 집합을 생성하거나 이미 생성된 세마포어에 접근하기 위해 사용한다.
semctl() 함수는 세마포어를 제어한다.
semop() 함수는 세마포어의 값을 변경한다.

sem_helper.h를 사용해 다음과 같이 sync_all_processes()를 구현할 수 있다[1].

#include "sem_helper.h"
 
void sync_all_processes ()
{
    int sem_id;
    int rc;
 
    /* Get semaphore */
    sem_id = get_semaphore();
 
    /* Decrement semaphore value */
    decrement_semaphore (sem_id);
 
    /* Now wait till semaphore value reaches 0 */
    wait_semaphore (sem_id);
}

이를 python과 fortran에 이식할 수 있도록 해야 한다.

References :
[1] Avadh Patel, Creating a Barrier between Processes with SysV Semaphore
[2] 주재경, 리눅스에서의 세마포어(1), http://www.hanbit.co.kr/network/view.html?bi_id=1398
[3] 주재경, 리눅스에서의 세마포어(2), http://www.hanbit.co.kr/network/view.html?bi_id=1399
[4] 세마포어, Joinc, http://www.joinc.co.kr/modules/moniwiki/wiki.php/Site/system_programing/IPC/semaphores
[5] semget() 세마포어 생성 및 접근, falinux, http://forum.falinux.com/zbxe/index.php?document_srl=427675&mid=C_LIB
[6] semctl() 세마포어 제어, falinux, http://forum.falinux.com/zbxe/index.php?document_srl=428639&mid=C_LIB
[7] semop() 세마포어 값을 변경, falinux, http://forum.falinux.com/zbxe/index.php?document_srl=428641&mid=C_LIB

Advertisements
Tagged with: , , , , , , , , , , , , , , , , , , , ,
Posted in 1) Memo

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

누적 방문자 수
  • 96,190 hits
%d bloggers like this: