++Memo

Ice Breaking PCIe interface (not included in spec)

2장이 시작되기 전 PCI 및 PCIe에 대한 기본적 지식이 필요함을 느껴 진행 한다. 

참조 자료:

1. mindshare에서 나온 PCIe pdf

2. PCIe 관련 블로그1 - 문c 블로그 - PCI subsytem

3. PCIe driver development for Exynos SoC by Samsung

4. Linux PCI drivers - Free Electrons

5. Overview of PCIe subsystem - Texas Instruments

6. PCI system architecture, Local Bus, Tutorial - Porto University

7. PCIe 관련 블로그2

8. http://egloos.zum.com/nimphaplz/v/5314763
9. https://wiki.qemu.org/images/f/f6/PCIvsPCIe.pdf
10. https://pcisig.com/sites/default/files/files/PCI_Express_Basics_Background.pdf#page=26
11. https://slidesplayer.org/slide/14669145/
12. https://wiki.osdev.org/PCI
13. https://static.lwn.net/images/pdf/LDD3/ch12.pdf
14. https://wiki.qemu.org/images/f/f6/PCIvsPCIe.pdf

Peripheral Component Interconnect Bus (PCI)

위키백과
PCI 버스는 컴퓨터 메인보드에 주변 장치를 장착하는 데 쓰이는 컴퓨터 버스의 일종이다.
이 장치는 다음과 같이 두 가지 형태로 나뉜다.
 1. 주기판 위에 바로 붙는 IC 형태 - PCI 스펙에서는 이러한 형태를 평면 장치(planar device)라고 부른다.
 2. 소켓에 꽂아 쓰는 확장 카드 형태 - 사용자 입장에서 흔히 눈에 띄는 형태이다.내가 본 PCI의 경우 2번의 형태가 많았다. 주로 sound card, ethernet card 등을 꽂아 사용한다.

PCI 특징

PCI는 이전의 ISA, MCA, EISA, VESA 버스를 대체하기 위해 설계 되었다. 

PCI는 아래의 특징을 가진다.

1. 빠른 전송 속도

   • 기존 bus들은 낮은 clock cycle (ISA: 4.7MHz, MCA: 10MHz, EISA: 8.3MHz, VESA: 33MHz)을 가진다.

   • PCI는 33MHz부터 266MHz 이상의 clock cycle을 가져 데이터의 빠른 전송이 가능하다.

2. 단일화된 인터페이스

   • CPU와 PCI bus 사이에 system/PCI bus bridge를 설치해 여러 프로세서를 위한 설계가 가능하다.

   • PCI bus에 PCI/Expansion bus bridge를 설치해 기존의 버스를 사용할 수 있다.

3. 동시에 여러개의 function을 지원 

   • 같은 PCI bus상에 여러 bus master가 존재할 수 있다.

   • 하나의 디바이스에 동시에 여러개의 function을 지원할 수 있다. 

PCI Express (PCIe)

위키백과
PCIe는 앞서 언급한 버스 표준들과 비교하여 높은 시스템 버스 대역폭, 적은 I/O 핀 수, 적은 물리적 면적, 버스 장치들에게 더 뛰어난 성능 확장성, 상세한 오류 검출 및 보고 구조(Advanced Error Reporting (AER), 핫-플러그 기능등 여러 장점을 가지고 있다. 최근에는 하드웨어 I/O 가상화도 지원한다\

PCIe 특징

PCIe는 기본적으로 PCI가 가지는 성능적 한계 및 신호 왜곡 등을 개선하기 위해 기존의 병렬 bus로 구성된 PCI의 bus를 serial bus로 바꿔 설계했다. PCIe는 PCI 슬롯을 그대로 사용하며 여러개의 슬롯을 공유하지 않고 1:1로 연결해 사용한다. 따라서, 여러 장치를 붙일 경우 PCIe switch를 사용해 다수의 End device를 연결할 수 있도록 한다.

PCIe의 장점은 아래와 같다.

1. Bandwidth의 증가
2. Bus clock cycle의 증가
3. Bus width의 감소
4. 회로의 단순화
5. PCI 디바이스 SW 호환성 유지

기본적으로 PCI는 병렬 bus를 이용하기 때문에 신호 왜곡에 취약하기 대문에 bus의 clock cycle을 올리기 어렵다. 이를 dual-simplex 방식의 serial bus로 바꿈으로써 bus width의 감소, clock cycle의 증가, 회로의 단순화 등의 장점을 가진다.

(참조: http://www.technoa.co.kr/news/articleView.html?idxno=38092)

PCIe Lane

Link

x1 ~ x32 lane을 하나로 묶어 사용할 수 있다. 

1개의 Lane은 TX와 RX로 dual-simplex 구성으로 되어 있으며, 1개의link는 End-to-End Device간 1:1로 통신이 가능하다.

Dual-simplex

단 방향으로의 데이터 bus가 2개 1개 set로 구성되어, 하나의 bus는 데이터를 보내고 다른 하나의 bus는 데이터를 받는 것에만 사용된다. PCIe는 기본적으로 2개의 데이터 전달 통로(lane)을 갖는다. 

*Full duplex도 존재 한다. 여러가지 방법이 존재 함.

PCIe Topology

위 그림은 PCIe를 통해 데이터를 전송하고자 하는 architecture의 topology를 나타낸다.

PCIe로 port를 연결하기 위해서는 기본적으로 Root Complex (RC)가 필요하다. 

RC는 CPU와 PCIe bus들 사이의 interface를 말하며 CPU interface, DRAM interface 등 여러가지 구성요소와 여러 개의 칩들을 포함한다. RC의 위치는 CPU내 (구글링 검색 결과), 메인보드 Chipset 내에 존재 한다.

전체 fabric의 instance들은 다음 구성요소이다.

1. Root Complex
2. Multiple endpoints (I/O devices)
3. Switch
4. PCIe to PCI/PCI-X bridge

Switch의 경우 위 그림 처럼 PCIe slot을 여러개 확장해서 사용할수 있도록 한다.

PCIe Root Complex (RC)

RC는 Host CPU와 연결하기 위한 host bridge device와 secondary device 연결을 위한 PCIe port가 존재 한다. 

Switch

1. Switch는 하나의 RC에 여러 디바이스를 붙일 수 있도록 만든 장치이다.
2. Swtich는 여러개의 Down-stream ports를 가지고 있지만 up-stream port는 하나만 존재 한다. 
3. 모든 활성화된 switch port는 flow control을 지원해야 한다. (Packet router처럼 동작하며, 해당 packet의 주소와 다른 routing 정보를 통해 어떤 경로로 packet이 가야하는지 인식한다.)

Endpoint Device

1. Endpoint device는 아래의 3가지 종류가 존재한다.
2. Legacy PCI endpoint
   • Type 0 configuration header를 제공하는 function이여야 함
   • I/O 요청 제공 및 발생 가능
   • 4GB (32bit 주소 register일때) 주소를 초과하는 memory transaction 불가
   • MSI/MSI-X를 지원
3. PCIe Endpoint
   • Type 0 configuration space를 제공하는 function이여야 함
   • I/O 요청 불가
   • 4GB 주소 범위를 넘는 memory transaction 가능 (64bit addressing 가능)
   • MSI/MSI-X 지원
4. Root Complex integrated endpoint
   • Type 0 configuration space를 제공하는 function이여야 함
   • Root complex 내부 로직에 구현된 root port
   • I/O 요청 불가
   • 전원 관리 구현 X
   • Hot plug 지원 X
   • MSI/MSI-X 지원
   • 32bit BAR를 통해 memory resource를 지원 (End-point device의 BAR와 비교한 결과 존재)

PCIe 계층 구조 및 데이터 전송

PCI 전송에는 3개(Transaction layer, Data link layer, Physical layer)의 layer가 필요하다. 

PCI -> PCIe 변화 (paralle bus -> serial bus)로 변경되는 부분은 Transaction, Data Link, Physical 계층이다.

아래는 데이터의 전송 과정을 요약했다.

1. Transaction layer에서는 packet 단위의 전송을 위해 데이터 packet을 형성하고 이를 Link layer로 전달한다.
2. Link layer에서 데이터의 신뢰도를 위한 CRC 코드를 전달 받은 데이터에 삽입한다.
3. Physical layer에서 frame 붙여 데이터를 추가 후 8b/10b 인코딩을 해 데이터를 전송하기 위해 serialized data로 변환한다.

Transaction layer에서 생성된 데이터 packet은 header와 data로 구성되어 있다. 해당 packet이 Data link layer로 전달되고 Data link layer에서 packet의 순서를 정한 번호와 CRC코드가 앞뒤로 붙게 된다. 그리고 Physical layer로 도착한 데이터에 대해 앞뒤로 frame을 붙이고 해당 packet을 serialize하며 이때 8b/10b 인코딩 시키면 PCIe bus를 통해 데이터를 전달하게 된다. 하지만 이것은 PCIe Gen 1 기준으로 나타냈다. Gen 3만 보더라도 encoding scheme이 128b/130b로 늘어났기 때문이다. 전송되는 packet의 구성과 크기는 아래와 같다.

1. Physical Layer
   • Framing
     • Start (1B)
     • End (1B)
2. Data Link Layer
   • Sequence Number (2B)
   • LCRC (1DW)
3.  Transaction Layer
   • Header (3~4DW)
   • Data (0~1024DW)
   • ECRC (1DW)

Transaction Layer

Ttransaction layer에 발생되는 packet을 Transaction Layer Packets (TLP)라 부른다. TLP는 routing mechanism 및 규칙에 따라 하나의 링크에서 다른 링크로 전달된다. 아래는 TLP가 접근하는 4개의 address spcae를 말한다. 즉, PCIe 디바이스에서 packets이 전달될때 아래의 분리된 주소 공간이 사용된다. (TLP header를 통해 구분한다)

1. Memory
   
   • Transaction types: Read, Write 
   • Purpose: transfter data to or from a location in the system memory map
2. I/O
   • Transaction types: Read, Write
   • Purpose: Transfer data to or from a location in the system IO map
3. Configuration
   • Transaction types: Read, Write
   • Purpose: Transfer data to or from a location in the configuration space of a PIC-compatible device
4. Message
   • Transaction types: baseline, vendor-specific
   • Purpose: general in-band messaging and even reporting without consuming memory or IO address resoures

Data Link Layer

• 링크 트레이닝
  • 링크 폭
  • 링크 데이터 rate
  • Lane reversal (Lane 역 방향 순서 지원)
  • Polarity inversion (극성 반대 지원)
  • 멀티 레인에서 레인 to 레인 de‐skew
• 전원 관리
  • 트랜잭션 게층에서 요청한 전원 상태를 수락하고 물리 계층으로 전달한다.
  • 활성/재설정/연결 해제/전원 관리 상태를 트랜잭션 계층으로 전달한다.
• 데이터 프로텍션, 에러 체킹
  • CRC 생성
  • 에러 체킹
  • 재전송 메시리지대한 TLP 응답
  • 에러 리포팅 및 로깅을 위한 에러 인디케이션

Physical Layer

• 인터페이스 초기화, 메인트넌스 제어 및 스테이터스 트래킹
  • 리셋/핫플러그 컨트롤
  • 전원 관리 인터커넥트
  • width & lane 매핑 협상
  • lane 극성 반전
• 심볼 및 오더
  • 8b/10b 엔코딩 및 디코딩
  • 임베디드 클럭 튜닝 및 정렬
• 심볼 전송 및 정렬
  • 전송 회로
  • 리셉션 회로
  • 수신 측 Elastic 버퍼
  • 수신 측 멀티 lane de-skew

1.1 Overview

NVMe interface는 host software가 non-volatile memory subsystem와 통신할 수 있도록 해준다.

NVMe는 PCIe interface를 사용하는 enterprise와 client SSD에 최적화되어 있다.

1.2 Scope

해당 spec은 NVM subsystem의 controller와 register interface를 정의한다.

세 종류의 Controller가 존재한다.

1. I/O controllers

2. Discovery controllers

3. Administrative controllers

1.3 Outside of scope

1.4 Theory of Operation

NVMe Interface는 최적화된 command submission과 completion paths를 제공한다.

Key attributes

• command submission 또는 completion path에서 uncacheable/MMIO register read가 필요하지 않다.

• command submmision path에서 최대 하나의 MMIO register wrtie가 필요하다.

• 최대 64K I/O queue 지원과 각 I/O queue는 64K개의 outstanding commands가 가능하다.

• 각 I/O queue와 관련된 priority는 well-defined arbitration mechanism으로 조정 된다.

• 4KB read 요청을 완료하기 위한 모든 정보는 64B command에 포함된다.

• 효율적이고 streamlined command set을 가진다.

• MSI / MSI-X와 interrupt 지원한다.

• Multiple namespaces 지원한다.

• SR-IOV처럼 효율적인 I/O virtualization을 지원한다.

• Robust error reporting과 management capabilities

• Multi path I/O와 namespace sharing을 지원한다.

NVMe controller는 single PCI function과 연관된다.

전체 controller에 적용되는 capabilities와 설정들은 Controller Capabilities (CAP) 레지스터와 Identify Controller data structure를 나타낸다.

하나의 namespace는 logical block으로 format된 non-volatile memory의 quantity이다.

NVMe controller는 namespace ID를 가지는 multiple namspaces를 지원한다.

Namspaces는 Namespace Management와 Namespace Attachment commands로 생성과 삭제가 된다.

Identify Namespace data structure는 특정 namespace의 capabilities와 설정을 나타낸다.

NVMe interface는 submission과 completion queue의 pair 형태를 기반으로 한다.

Commands는 host software에 의해 submission queue에 issue 된다.

Completions는 controller에 의해 completion queue에 issue 된다.

Multiple submiision queues는 동일한 completion queue를 이용한다.

Submission과 complition queues는 메모리에 할당 된다.

Admin submission과 이와 관련된 completion queeu는 controller 관리, I/O submission과 completion queues들의 생성과 삭제 및 aborting commands 등 control 목적을 위해 존재한다.

I/O command set은 I./O queue pair로 사용된다.

해당 spec에서는 I/O command set을 NVM command set으로 명시한다.

Queue pair

• Host software는 controller가 지원하는 최대 개수의 queue를 생성한다.

• queue 생성은 system configuration과 anticipated workload에 기반한다.

• queue 생성의 종류는 1:1 mapping, n:1 mapping이 존재 한다.

Submission Queue와 Completion Queue를 이용한 I/O 처리 과정

• Submission Queue (SQ)는 host software가 controller에 의해 실행되기 위한 commands를 전달하기 위한 고정된 크기의 circular buffer이다

• 실행되어야 할 1~n개의 새로운 commands이 있다면 host software는 적절한 SQ Tail doorbell 레지스터를 업데이트 한다. 

• 새로운 doorbell resister write가 있을때 이전의 SQ tail 값을 덮어 쓰기한다.

• Controller는 SQ entries을 SQ에서 순차적으로 fetch하고 어떤 순서로(알고리즘에 기반) 실행한다.

• 각 SQ entry는 command이고 64B의 크기를 가진다.

• 메모리내 Physical 메모리는 data 전송을 위해 사용되며, Phsical Region Page (PRP) entries 또는 Scatter Gather Lists가 나타낸다.

• 각 command는 두개의 PRP entires 또는 하나의 SGL segment를 포함한다.

• 만약 data buffer를 위해 두개 이상의 PRP entires가 필요하다면, PRP Lists의 pointer가 PRP entires를 가리킨다.

• 위와 동일하게 하나 이상의 SGL이 필요한 경우, SGL semgment는 다음 SGL segment pointer를 제공한다.

• Completion Queue (CQ)는 completed command의 상태를 나타내기 위한 고정된 크기의 circular buffer이다. 

• Completed command는 host software에서 할당된 SQ identifier와 comand identifier의 조합으로 식별된다.

• Multiple SQ는 하나의 CQ를 사용한다. 

Multi-Path I/O and Namespace Sharing

• Multi path I/O는 하나의 host와 하나의 namespace 사이간에 두개 이상의 독립된 path를 말한다.

• 반면에 namespace sharing은 두개이상의 host가 다른 NVM controller를 사용하는 shared namespace에 접근하는 것을 말한다. 

1.5 Conventions

Abbreviations

• RO : Read Only

• RW : Read Write

• R/W : Read Write. The value read may not be the last value written.

• RWC : Read/Write '1' to clear

• RWS : Read/Write '1' to set

• Impl Spec : Implementation Spec

• HwInit : The default state is dependent on NVMe controller and system configuration

• Reset : This column indicates the value of the field after a reset

Use a '0's based value 

1.6 Definitions

Admin queue

• identifier 0을 가지는 SQ와 CQ이다.

• administrative commnad를 submit하고 completions을 받기 위해 admin SQ와 admin CQ는 pair를 이룬다.

Administrative controller

• Host가 NVM subsystem을 관리할수 있도록 capabilities를 가지고 있는 controller

• 해당 controller는 I/O queues를 가지지 않는다.

• Logical blocks과 관련된 metadata 또는 data에 대한 접근을 제공한다.

• namespaces를 지원한다.

Arbitration burst

• Round robin 또는 weighted round robin을 사용하는 SQ로부터 한번에 처리 가능한 commands의 최대 수를 말한다.

Arbitration mechanism

• SQ에서 Controller에 의해 수행되기 위한 command를 결정하기 위해 사용 된다.

Cache

• NVM subsystem을 사용하는 data storage area

Command completion

• Controller가 command를 처리한 command

• 처리 결과 상태는 completion queue entry에 업데이트 된다.

Command submission

• Command는 SQ Tail doorbell write는 처리되었을때 submmit 된다. 

Controller

• Types

  • I/O controllers

  • Discovery controllers

  • Administrative controllers

• Controller는 host에 의해 SQ에 submmit된 commands를 실행하고 completion queue에 completion을 업로드 한다.

• 각 controller는 하나의 admin SQ와 하나의 admin CQ를 가진다.

• Controller에 따라 하나 이상의 I/O queues를 가질수 있다.

directive

• host와 NVM subsystem 또는 controller 정보를 교환하는 방법이다.

• 정보는 Directive Send와 Directive Receive commands를 통해 전달된다.

•  I/O commands의 subset은 I/O command와 관련된 정보를 통신하기 위해 Directive Type field와 Directive Specfic field를 포함한다.

Discovery controller

• Host가 Discovery Log Page 정보를 받을수 있도록 하는 특성을 가진 controller이다.

• I/O queues를 가지지 않는다. 

Emulated controller

• Software에 정의된 NVMe controller이다. 

Endurance Group

• NVM subsystem내 NVM 중 일부이다.

• Group 으로 endurance가 관리된다.

extended LBA

• 연속적인 LBA 전송과 관련된 memta가 전송될때 생성된다.

firmware slot

• NVM subsystem내에서 firmware image를 저장하기 위해 사용되는 슬롯이다. 

• NVM subsystem은 1~7개 firmware images를 저장할 수 있다.

I/O completion queue

• I/O completion queue는 completion queue이다. 

• 하나 이상의 SQ와 연관되며, I/O CQ identifiers는 64K까지 값을 가진다.

I/O submission queue

• I/O submission queue는 SQ이다. 

• Controller에 의해 실행하기 위한 I/O command를 SQ에 submit한다.

I/O controller

• I/O queues를 가지는 controller이다. 

• NVM storage를 접근하기 위해 사용된다.

LBA range

• 연속적인 logical blocks의 범위이다.

Logical block

• 가잔 작은 접근 가능한 data 단위이다.

Logical block address (LBA)

• Logical block의 주소이다.

metadata

• 특정 LBA 데이터에 대한 정보이다.

primary controller

• Virtualization Management command를 지원하는 NVMe controller이다.

참조: http://esos.hanyang.ac.kr/?page_id=13347

       http://esos.hanyang.ac.kr/?page_id=15843

주제 1. 리눅스의 대용량 메모리 관리 기법 분석

현재 PC 시장에서 DRAM 메모리의 용량은 크게 증가되었으며, 메모리 집적화 기술의 고도화로 인해 대용량 서버 환경에서는 TB 단위의 메모리까지 등장하게 되었다. 하지만 이와 같은 물리 메모리의 증가는 CPU의 하드웨어 캐시인 TLB(Translation Look-aside Buffer)의 잦은 Miss를 통해 전체적인 메모리 작업의 성능을 하락시키는 문제를 발생시켰다. 때문에 리눅스에서는 하나의 페이지의 크기를 2MB, 1GB까지 확장하도록 지원하는THP(Transparent Huge Page)기법을 제공한다. THP 기법은 하나의 TLB에서 관리할 수 있는 페이지의 크기를 늘려, 기존의 TLB로도 효율적으로 대용량 메모리를 관리할 수 있도록 하는 장점이 있다. 하지만, THP 기법은 비효율적인 메모리 할당 정책 및 페이지 할당에 걸리는 시간이 매우 크다는 단점이 존재하기에 아직 완벽한 기법이 아니다. 본 프로젝트에서는 이러한 리눅스의 THP 기법을 코드 단위로 분석하여 그 동작 방식을 이해하며, 대용량 메모리 경에서의 THP 기법 사용의 장단점을 분석한다. 본 프로젝트는 분석을 위해 Sysbench, Cloudstone, Redis, MongoDB 등 DB환경에서의 성능 분석 툴을 사용하여 Buffered I/O의 지연 시간 및 물리 메모리 사용량을 측정한다. 이러한 분석과정을 통해 리눅스에서 THP 기법의 동작 방식에 대한 장단점 파악 및 개선 방안을 고안한다. 본 프로젝트는 리눅스의 물리 메모리 관리 기법에 대한 이해를 우선할 수 있음은 물론, 리눅스 기반 대용량 메모리 시스템에 최적화 된 메모리 관리 방식을 설계하는 것을 목표로 한다.

프로젝트 완성도 : 최종 보고서, 발표 자료, 소스코드, Transparent Huge Page 개선 방안 등

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 2. EXT4의 Buffered Write 성능 개선

사용자 프로세스가 특별한 플래그(O_DIRECT, O_SYNC) 없이 일반적인 방법으로 열린 파일에 대해서 쓰기(write())를 수행하면, 리눅스 커널은 사용자가 쓰기를 요청한 내용을 디스크 내 파일에 바로 쓰지 않고, 메모리 내 페이지 캐시에서 페이지를 할당 받아 페이지에 내용을 쓴다. 해당 페이지는 더티 페이지로 구분되고, 추후 커널 쓰레드에 의해 파일에 쓰여진다. 이를 Buffered 쓰기라고 한다. Buffered 쓰기를 사용함으로써 사용자 프로세스는 쓰기(write())를 빠르게 수행할 수 있다. 하지만, 사용자 프로세스가 4KB Buffered 쓰기를 과도하게 하면, write() 시스템 콜의 Latency가 1초 이상으로 증가하는 것을 볼 수 있다. EXT4 파일 시스템에서 write() 시스템 콜의 Latency 증가 원인은 쓰기를 수행할 페이지를 할당하는 ext4_write_begin():fs/ext4/inode.c 함수와, 해당 더티 페이지로 구분하고, Buffered 쓰기 동작을 마무리하는 ext4_write_end():fs/ext4/inode.c 함수이다. 본 프로젝트에서는 write() 시스템 콜 Latency 증가의 원인이 되는 두 함수(ext4_write_begin():fs/ext4/inode.c, ext4_write_end():fs/ext4/inode)의 동작을 분석하고, 해당 함수의 동작 중 어떤 부분이 Latency 증가 원인인지 파악 후, 원인이 되는 동작이 write() 시스템 콜 Latency 증가에 영향을 끼치지 않도록 수정하는 방안을 고안하여 수정한다. 그리고, 수정한 EXT4 파일 시스템과 수정하지 않은 기존의 EXT4 파일 시스템에서 동일한 실험(30 Gbyte 이상의 Buffered 쓰기)을 통해 write() 시스템 콜의 지연 시간을 측정하여 성능향상을 확인한다.

프로젝트 완성도 : 최종 보고서, 발표자료

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 3. EXT4, F2FS, XFS에서의 fsync() 동작 및 성능  분석

fsync()는 파일시스템의 dirty block을 디스크로 플러시 하는 함수이다. 리눅스 시스템 컬중 가장 중요하고 시간이 많이  소요되는 연산이다. fsync()는 입출력 스케쥴링, 파일 시스템 저널링등 모든 분야에 다 걸쳐있다. 본 프로젝트에서는  ext4, f2fs, xfs 파일 시스템의 fsync() 알고리즘을 분석 비교 한다. 그리고, 4KByte 임의 쓰기 실험을 통해 장단점을 비교 분석해 보기로 한다. 분석은 성능과함께 입출력 트레이스를 출력한다. 리눅스 커널의 심도있는 이해를 위한 매우 좋은 주제이다.

프로젝트 제출물 : 최종 보고서, 발표자료

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 4. F2FS 파일 시스템의 세그멘트 클리닝 분석 및 개선

 F2FS는 플래시 전용으로 개발된 로그기반 파일 시스템이다. 현재 화웨이사의 안드로이드 스마트폰인  P9, 구글 NEXUS 9 태블릿등에 탑재되어 시판되고 있다. 로그기반 파일 시스템은 무효화된 블럭을 소거하는 비용이 매우 높은 것으로 알려져있다. 본 프로젝트에서는 F2FS의 GC 알고리즘을 분석하고, 블록을 효율적으로 분리하는 알고리즘을 개발한다.

프로젝트 완성도 : 최종 보고서, 발표 자료

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 5. 리눅스 블록 계층의 멀티 큐 메커니즘 분석 및 개선

오늘날 컴퓨터 시스템에서 저장 장치는 HDD에서 보다 빠른 SSD로 대체되고 있고, 더 나아가 최근에는 PCIe를 이용하는 NVMe(Non-Volatile Memory Express)를 저장 장치로 효율적으로 사용하기 위한 연구가 활발히 진행되고 있다. NVMe는 최대 64K개의 하드웨어 큐를 제공하여, 많은 I/O 요청을 한꺼번에 병렬로 처리하는 것이 가능하다. 리눅스는 이러한 하드웨어 멀티 큐를 사용하는 저장 장치를 지원하기 위해 Multi-Queue block layer를 제공한다. 본 프로젝트에서는 리눅스의 Multi-Queue block layer를 제안한 “Linux Block IO: Introducing Multi-queue SSD Access on Multi-core Systems” 논문을 통해 Multi-Queue block layer의 구조를 이해하고, Multi-Queue block layer 소스코드(block/blk-mq*)와 Multi-Queue block layer를 사용하는 디바이스 드라이버(drivers/nvme/*)를 분석하여I/O 처리 흐름을 파악한다. 마지막으로 IOZone, Mobibench, Filebench 등의 I/O 벤치마크 툴을 사용하여 Single-Queue와 Multi-Queue의 latency를 측정하고, 측정한 값이 위 논문에서 제시하는 성능과 차이가 있는지 비교 분석하는 것을 최종 목표로 한다. Multi-Queue block layer 분석은 리눅스 커널의 블록 계층을 심도있게 이해할 수 있는 좋은 주제이다.

프로젝트 완성도 : 최종 보고서, 발표 자료

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 6. 리눅스 I/O 스케줄러 분석 및 개선

리눅스 운영체제의 I/O 스케줄러와 다양한 입출력 조건에 따른 입출력 성능의 상관관계를 분석한다. 리눅스는 파일 시스템에서 요청한 입출력을처리(Merging, Sorting)하기 위해 CFQ, Deadline, Noop 등 다양한 스케줄링 기법을 제공하고 있으며 I/O 스케줄러는 각각 장*단점을 가지고 있다. 예를 들면, CFQ 스케줄러의 경우, I/O 처리에 있어서 공평성(Fairness)를 제공하지만 I/O 처리의 지연 시간(Response time)이 비교적 길다는 단점이 있으며 반대로 Deadline 스케줄러는 I/O 지연을 최소화할 수 있으나 I/O의 공평성을 제공하지는 못한다. 본 프로젝트에서는 스케줄러의 입출력 처리 과정을 코드 레벨(linux/block/blk-core.c, cfq-iosched.c, deadline-iosched.c, noop-iosched.c)로 확인하고 실제 성능 측정을 통해 I/O 스케줄러가 수행되는 입출력 조건(ex> Storage type, Workload 등)이 실제 I/O 처리 과정에 끼치는 영향을 분석한다(사용 벤치마크 툴: IOZone, Mobibench, Filebench). 또한 분석 결과를 근거로각 I/O 스케줄러의 처리 기법 상의 장*단점을 분석하고 개선안을 도출하여I/O 스케줄러의 성능을 향상시키는 것을 목적으로 한다.

프로젝트 완성도 : 최종 보고서, 발표 자료, 소스코드

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 7. 안드로이드를 위한 리눅스 메모리 매니저 분석 및 개선

리눅스 운영체제의 메모리 할당기는 안드로이드에는 적합하지 않은것으로 알려져있다. 때문에 많은 내부 파편화가 발생하고 메모리가 낭비되는 것으로 알려져 있다.파편화란, 메모리 내의 빈공간이나 자료가 여러 개의 조각으로 나뉘는 현상을 말한다. 데이터의 크기가 다양하기 때문에 발생하는 현상으로, 파편화가 심할 경우 성능 저하가 발생하고, 여유 공간이 충분히 있어도 할당이 실패하는 현상이 발생할 수도 있다.  본 주제에서는 리눅스의 메모리 할당기 작동을 심도있게 분석하고, 안드로이드 상에서 물리메모리가 할당되는 과정을 살펴본다. 본 프로젝트는 리눅스 운영체제의 메모리 매니저의 장단점을 분석하고, 메모리 할당, 해제, 파편화 등을 분석하는 것을 목표로 한다. 리눅스의 메모리 할당 기법을 심도있게 파악하는 매우 좋은 기회이다.

프로젝트 완성도 : 최종 보고서, 발표 자료, 소스코드, 메모리 분석 결과 등

자격 요건 : 자료구조, 운영체제, C (리눅스 커널 사전지식 불필요)

주제 8. SQLite용 저널모드 분석 및 개선

SQLite는 안드로이드, 아이폰, 타이젠, 파이어폭스등 다양한 모바일 기기에서 공통적으로 사용되는 오픈소스 임베디드 데이타베이스이다. 오픈소스 장점으로 인해 광범위하게 사용되고 있다. SQLite는 비효율적인 저널링 동작으로 인해 과도한 입출력을 발생시킨다. 스마트폰 업계에서는 SQLite의 입출력 작동을 효율화 시키는 것을 매우 중요한 주제로 삼고 있다. 본 주제에서는 SQLite의 저널 모드에 대해 학습하고, 가능한 개선 방법을 모색하도록 한다.

주 : 안드로이드 디바이스 지급

프로젝트 완성도 : 최종 보고서, 발표 자료, 소스코드, SQLite 성능 개선 방안 등

자격 요건 : 자료구조, 운영체제, C (안드로이드 사전지식 불필요)

주제 9. SSD 시뮬레이터 개발

플래시 기반의 SSD는 현대 저장장치기술의 핵심이다. 새로운 저장장치 알고리즘을 개발함에 있어서 새로운 SSD기술을 효율적으로 개발하기 위해서는 하드웨어 개발 이전에 시뮬레이터를 통해서 개발된 기술의 유효성을 검증하는 것이 필수이다. 본 과제에서는 한양대학교에서 개발하여 현재 널리 사용되고 있는 오픈소스 시뮬레이터인 VSSIM 을 개선한다. VSSIM은 오픈 소스 기반  SSD 이뮬레이터이다. SSD의 채널/웨이등을 변경할 수 있고, 이와더불어 다양한 SSD의 매핑 알고리즘과 Garbage Collection 알고리즘을 적용할 수 있다. 이를 다음과 같이 개선한다. 본 주제에서는 SSD용 시뮬레이터 VSSIM에 대해서 학습하고, 다양한 개선점을 모색한다.

– 최신 qemu로 포팅
– 다중 쓰레드 지원
– PCIe 지원

주 : 오픈소스 활동

프로젝트 완성도 : 최종 보고서, 발표 자료, 소스코드, 알고리즘, 성능 개선 방향 등

자격 요건 : 자료구조, 운영체제, C, 핀토스 사전지식 필요

주제 10. MongoDB 분석및 개선

mongdb는 현재 다양한 웹사이트에서 사용되는 효율적인 데이타베이스 이다.  블로그, 게임아이템 저장을 위해서 사용되는 가장 대중적인 자료구조이다. 몽고 DB의 핵심인 LSM tree가 어떤것인지 살펴보고 그의 동작을 분석해본다. LSM tree 가 많이 사용되는 Redis, Cassendra등의 성능을 분석한다.

프로젝트 완성도 : 최종 보고서, 발표 자료등

자격 요건 : 자료구조, 운영체제, C (안드로이드 사전지식 불필요)

https://docs.simplessd.org/index.html

http://camelab.org/pmwiki.php/Main/Tools

https://github.com/MatiasBjorling/flashsim

출처: http://ssu1945.egloos.com/4007260

NVMe 는 실제 Command단위로 움직이는 Protocol Layer

그 밑의 Transport, Link, Physcal (SATA  기준으로) Layer는 PCIe 의 spec.을 따릅니다.

그리고 보통 S/W 가 작업하는 F/W level 은 Protocol Layer 부분부터 가져오게 됩니다.

아래 그림에서 NVMe Protocol 이 정의 하는 내용은 Software layer 이다.

그 밑단의 일련의 작업들은 실제로 PHY chip 이라 불리우는 H/W가 작업을 해줍니다.

실제 S/W engineer 가 신경써야 하는 것은 Software layer 이다.

그럼 H/W 만 믿으면 되지 않느냐? 라고 하겠지만 실제 Data의 순서 및 PCI device로의 인식등 여러가지 문제들을 생각하고 구현해야 SSD를 만들수 있어요.

그래서 NVMe spec.의 2장은 System Bus (PCI Express) Registers 라고 이름 붙여져 있습니다.

PC 에서 Power ON 이 되면 Mainboard 의 F/W 인 BIOS 에서 PCI device를 인식합니다.

인식한 뒤에 Link layer 에서 Link 부분의 조율(한국어로는 조율이라는 표현이 제일 맞을것 같네요.)을 합니다.

(Link와 Physical 부분은 제가 전문가는 아니라서 정확히는 모르고 PCI 와 SATA 가 Speed set 부분에 있어 순서가 다른데 정확한 정보 확인 뒤에 업데이트 하도록 하겠습니다.)

Link 부분이 정확히 끝난뒤에 실제 PCI device로 부터 PCI header 를 읽어 갑니다.

이때 부터 PCI device 인지 알게 되는 거죠. 

PCI slot을 보통 그래픽 카드나 랜카드, 사운드 카드를 사용하시는데 많이 쓰셨을껀데, Device ID 중에 mass storage가 있습니다.

PCIe Header 까지 설명하면 너무 길어지니 적당히 이야기 할게요.

Header 안에는 device 의 vendor(회사명 입니다. PCI sig 에 등록된 생산회사명), Device ID(PCI 에 붙은 장치의 종류 : 그래픽 카드라던가...), BAR, Expansion ROM Address 등등이 적혀 있고, 이부분을 다 읽어가고 나면 이제 NVMe device 로서 인식을 하고 NVMe 명령어를 던지게 됩니다.

기본적으로 NVMe 명령어도 TLP 단계로 내리면 PCIe로 감싸지기 때문에 위에서 바라볼때만 NVMe 인거지 그 밑단에서는 PCIe 와 다를게 없어요.

그래서 NVMe 를 심도 있게 보시려면 PCI 의 TLP 까지는 보셔야 제대로 보실수 있습니다.

또한 PCIe 를 사용하는 만큼 커넥터 역시 여러가지를 쓰는데요.

우리가 알고 있는 PCIe slot 이외에  M.2 또는 SFF 8639 가 있는데요.

이부분은 SATA, SAS, PCIe 가 모두 활용할 수 있는 부분입니다.

자세한 부분은 구글링 몇번이면 나올거에요. 아래자료에 보면 NVMe 에서 어떻게 설명하고 있는지 나옵니다.

(참조 : http://nvmexpress.org/wp-content/uploads/2013-FMS-NVMe-Track.pdf )

결국 PCIe 를 사용하는 입장이기에 PCIe를 어느정도 알지 못하면 NVMe 자체를 잘 사용할수 없다가 결론입니다.

PS : NVMe spec. 2장을 공부하시다가 궁금하신건 PCIe spec. 3.0 을 보세요. 전에 언급했던 대로 Mindshare 자료 좋습니다. 참고하세요.