Description

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom. The detail images are below:

Implementation

This is basically, we’re looking at the binary tree from right side. In the first example, the output would be [1,3,4]. In here, we can think that we can just traverse right side, but the next example shows that we can’t just look at the right traversal. nodes that are hide, show in the left root tree. So how do we approach to this problem. Since binary tree is part of complete binary tree, we can do level-order traversal.

The level traversal is basically below in c++.

vector<vector<int>> levelOrder(Node *root) {
    if (root == nullptr)
        return {};

    // Create an empty queue for level order traversal
    queue<Node *> q;
    vector<vector<int>> res;

    // Enqueue Root
    q.push(root);
    int currLevel = 0;

    while (!q.empty()) {
        int len = q.size();
        res.push_back({});

        for (int i = 0; i < len; i++) {

            // Add front of queue and remove it from queue
            Node *node = q.front();
            q.pop();

            res[currLevel].push_back(node->data);

            // Enqueue left child
            if (node->left != nullptr)
                q.push(node->left);

            // Enqueue right child
            if (node->right != nullptr)
                q.push(node->right);
        }
        currLevel++;
    }
    return res;
}

Then let’s solve it. let’s use deque instead because it’s efficient! What we want is we are going to use levelLength which it comes from the idea of complete tree. If the size is not equal to q.size() - 1, it’s the left view, and if it’s same it’s going to be right view.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
vector<int> rightSideView(TreeNode* root) {
    vector<int> result;
    if (root == nullptr) return result;
    deque<TreeNode*> q;
    q.push_back(root);
    
    while(!q.empty()) {
        int lvlLength = q.size();
        for (int i = 0; i < lvlLength; i++){
            TreeNode* node = q.front();
            q.pop_front();
            // forces to get the right value 
            if (i == lvlLength - 1) {
                result.push_back(node->val);
            } 
            if (node->left != nullptr) {
                q.push_back(node->left);
            }
            if (node->right != nullptr) {
                q.push_back(node->right);
            }
        }
    }
    return result;
}

Resource

BST in Right Side View

Description

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.

Implementation

1. This problem resembles a typical graph problem, where detecting cycles is crucial. While DFS can be used with states like visited, not visited, and visiting, we’ll employ topological sorting via Khan’s algorithm instead. This choice is suitable for our needs because it efficiently orders nodes in a directed acyclic graph (DAG), which is relevant if we assume the graph doesn’t contain cycles.

2. Topological sorting relies on the indegree of nodes. Nodes with an indegree of 0, meaning they have no incoming edges, are always placed at the front of the queue. This is because they have no dependencies and can be processed immediately.

3. edges are pointed to 0 -> 1 (in order to take 0, we need to take 1)

what we need to prepare is the result vector, and the inDegree vector adjacent link list (link list can be just vector).

vector<int> result;
vector<int> inDegree(numCourses, 0);
vector <int> adj[numCourses];

Then, we would have to everything we need. From prerequsites vector, we would need to push the course we need to take, then directed to prerequsite node(class). Then we increment inDegree vector. why are we increasing the inDegree vector, because we need to tell that there is edge points to 1 (in above example)

for (auto x : prerequisites) {
    adj[x[0]].push_back(x[1]);
    inDegree[x[1]]++;
}

Then, we need to prepare for the queue, and check if the indegree is 0, which means it’s gonna be first to check. Then, we’re gonna check the outgoing edge from each node, and we are going to get rid of that edge (-=). Then, there is no incoming edge, then we push to the queue. Then we just have to check whether the size is equal or not to number of courses.

queue<int> q;
for(int i = 0; i < numCourse; i++) {
    if (inDegree[i] == 0) q.push(i)
} 

while(!q.empty()) {
    int val = q.front();
    q.pop();
    result.push_back(val);

    for(auto edge : adj[val]) {
        inDegree[edge] -= 1;
        if (inDegree[edge] == 0) q.push(edge);
    }
}

return result.size() == numCourse;

Resource

Course Schedule

• Reviewing what I studied, how this work will be explained as well.

Network Flow & Flow Graph

A flow graph (flow network) is a directed graph where each edge (also called an arc) has a certain capacity which can receive a certain amount of flow. The flow running through an edge must be less than or equal to the capacity. Think of this way, we have a path from Chicago to Boston, and Boston to New York. From Chicago to Boston (6 cars allowed per min) & Boston to New York (3 cars allowed per min). Then after 1 min, the state would be 3 cars are still waiting to go to Boston, and 3 cars are already in New York. So, how do we solve it? We just send 3 cars in the beginning. In this case, we are going to define some terms ‘flow’ / ‘capacity’.

Ford Fulkerson Method & Edmonds-Karp

Problem Statement:

One of the special things about Ford Fulkerson Methods is that there are sink node and source node (think of source node as faucet, and the sink as drainer). To find the maximum flow (and min-cut as a byproduct), the Ford-Fulkerson method repeatedly findsaugmenting paths through the residual graph and augments the flow until no more augmenting paths can be found. Then what the heck is an augmenting path? The definition of an augmenting path is a path of edges in the residual graph with unused capacity greater than zero from the source to sink.

The reason why it’s stated as a method, not an algorithm is because of flexibility in selecting augmenting paths (unspecified by Ford Fulkerson Method). If the DFS algorithm is chosen to get the augmenting path, every augmenting path has a bottleneck. The Bottleneck is the “smallest” edge on the path. We can use the bottleneck value to augment the flow along the paths. You can actually look at the image below, and the operation is min(10-0, 15-0, 6-0, 25-0, 10-0) = 6. (bottleneck value shown below)

we mean updating the flow values of the edges along the augmenting path. For the forward edges, this means increasing the flow by the bottleneck value. Also, when augmenting the flow along the augmenting path, you also need to decrease the flow along each residual edge by the bottleneck value. Then why are we decreasing the flow? Because what we want to achieve is to get the max flow, which requires considering all cases to fill the flows. By using the decrease, residual edges exist to “undo” bad augmenting paths which do not lead to a maximum flow.

we can define the residual graph. The residual graph is the graph which contains residual edges, as shown below:

Then, we could ask ourselves is “Residual edges have a capacity of 0? Isn’t that forbidden? How does that work?”. You might be able to think of the remaining capacity of an edge e (residual or not) as: e.capacity - e.flow. This ensures that the remaining capacity of an edge is always non-negative.

So, let’s wrap it up: the Ford-Fulkerson method continues finding augmenting paths and augments the flow until no more augmenting paths from s->t exist. The sum of the bottlenecks found in each augmenting path is equal to the max-flow. (So it doesn’t really matter how you find the augmenting path). The basic steps are:

1. Find an augmenting path
2. Compute the bottleneck capacity
3. Augment each edge and the total flow

Edmonds-Karp Algorithm

The Edmonds-Karp algorithm is a specific implementation of the Ford-Fulkerson method. The key difference is that Edmonds-Karp uses Breadth-First Search (BFS) to find augmenting paths, whereas the general Ford-Fulkerson method doesn’t specify how to find these paths.

By using BFS, Edmonds-Karp guarantees finding the shortest augmenting path (in terms of number of edges) at each step. This leads to a better time complexity than using arbitrary path-finding methods.

The time complexity of Edmonds-Karp is O(V × E²), where V is the number of vertices and E is the number of edges in the graph. This is a significant improvement over the general Ford-Fulkerson method, which has a time complexity of O(E × f), where f is the maximum flow value (which could be very large if edge capacities are large).

Implementation

class FordFulkerson
{
public:
	vector<bool> marked;
	vector<FlowEdge*> prev;
	double value;

	FordFulkerson(FlowNetwork& g, int s, int t)
		: marked(g.V), prev(g.V), value(0.0){
		while (HasAugmentingPath(g, s, t))
		{
			// Find the minimum Flow from the path
			double bottlNeck = numeric_limits<double>::max();
			for (int v = t; v != s; v = prev[v]->Other(v)) {
				bottlNeck = min(bottlNeck, prev[v]->ResidualCapacityTo(v));
			}

			for (int v = t; v != s; v = prev[v]->Other(v)) {
				prev[v]->AddResidualFlowTo(v, bottlNeck);
			}

			value += bottlNeck;
			Print(g);
		}
	}

	bool HasAugmentingPath(FlowNetwork& g, int s, int t) {
		fill(marked.begin(), marked.end(), false);

		queue<int> q; // BFS

		marked[s] = true;
		q.push(s);

		while (!q.empty())
		{
			int v = q.front();
			q.pop();

			for (FlowEdge* e : g.Adj(v))
			{
				int w = e->Other(v);
				if (!marked[w] && e->ResidualCapacityTo(w) > 0) // <- TODO: BFS와의 차이 확인
				{
					prev[w] = e;
					marked[w] = true;
					q.push(w);
				}
			}
		}

		return marked[t];
	}
};

Min-Cut Theorem

One of the most important results in network flow theory is the Max-Flow Min-Cut Theorem. This theorem states that the maximum flow in a network equals the capacity of the minimum cut.

A cut in a flow network is a partition of the vertices into two disjoint sets S and T, where the source s is in S and the sink t is in T. The capacity of a cut is the sum of the capacities of the edges going from S to T.

After the Ford-Fulkerson algorithm terminates, the min-cut can be found by:

1. Running a DFS or BFS from the source in the residual graph
2. Vertices reachable from the source form set S, the rest form set T
3. The edges going from S to T in the original graph form the min-cut

This min-cut represents the bottleneck in the network - the set of edges that, if removed, would disconnect the source from the sink.

Resource

• Max Flow Ford Fulkerson
• Max Flow
• Edmonds-Karp Algorithm

swift 에서의 struct 또는 class 에서는 member variable 을 property 라고 한다. 이 Property 들은 상태를 체크 할수 있는 기능을 가지고 있다. 천천히 알아보자.

• Store Property: member variable 결국, 상수 또는 변수를 저장한다고 보면된다. 이부분은 init() 에 instantiate 할때 설정을 해줘야한다.
• Type Property: static variable 이다. 객채가 가지고 있는 변수라고 생각하면 된다. 여러가지의 Instantiate 을 해도 공유 되는 값이다.
• Compute Property: 동적으로 계산하기 때문에, var 만 가능하며, getter / setter 를 만들어줄수있다. getter 는 필수 이며, setter 는 구현 필요없다. (즉 setter 가 없다면, 굳이 getter 를 사용할 필요 없다.)
• Property Observer: 이건 Property 들의 상태들을 체크를 할 수 있다. 상속받은 저장/연산 Proprty 체크가 가능하며, willSet 과 didSet 으로 이루어져있다. willSet 같은 경우, 값이 변경되기 전에 호출이되고, didSet 은 값이 변경 이후에 호출한다. 접근은 newValue 와 oldValue 로 체크할수 있다.
• Lazy Stored Property: 이 부분은 lazy 라는 Keyword 로 작성이되며, 값이 사용된 이후에 저장이 되므로, 어느정도의 메모리 효율을 높일수 있다.

import Foundation

struct AppleDevice {
    var modelName: String
    let releaseYear: Int
    lazy var care: String = "AppleCare+"
    
    /// Property Observer
    var owner: String {
        willSet {
            print("New Owner will be changed to \(newValue)")
        }
        
        didSet {
            print("Changed to \(oldValue) -> \(owner)")
        }
    }
    
    /// Type Property
    static let companyName = "Apple"
    
    /// Compute Property
    var isNew: Bool {
        releaseYear >= 2020 ? true : false
    }
}


var appDevice = AppleDevice(modelName: "AppleDevice", releaseYear: 2019, owner: "John")
print(appDevice.care)
appDevice.owner = "Park"

Instance Method 도 마찬가지이다. 위의 코드에 method 를 넣어보자. struct 일 경우에는 저장 property 를 method 에서 변경하려면, mutating keyword 가 필요하다. 그리고 다른건 static 함수이다. 이 부분에 대해서는 따로 설명하지 않겠다.

import Foundation

struct AppleDevice {
    var modelName: String
    let releaseYear: Int
    lazy var care: String = "AppleCare+"
    var price: Int
    
    /// Property Observer
    var owner: String {
        willSet {
            print("New Owner will be changed to \(newValue)")
        }
        
        didSet {
            print("Changed to \(oldValue) -> \(owner)")
        }
    }
    
    /// Type Property
    static let companyName = "Apple"
    
    /// Compute Property
    var isNew: Bool {
        releaseYear >= 2020 ? true : false
    }
    
    mutating func sellDevice(_ newOwner: String, _ price: Int) -> Void {
        self.owner = newOwner
        self.price = price
    }
    
    static func printCompanyName() {
        print(companyName)
    }
}


var appDevice = AppleDevice(modelName: "AppleDevice", releaseYear: 2019, price: 500, owner: "John")
print(appDevice.care)
appDevice.owner = "Park"
AppleDevice.printCompanyName()

Before we start

Let’s review the @State keyword. In order for View to notice, that the value of @State change, the View is re-rendered & update the view. This is the reason why we can see the change of the value in the View.

StateObject & ObservableObject

Now, let’s talk about StateObject & ObservableObject. If we have a ViewModel, called FruitViewModel, as below. Let’s review the code. FruitViewModel is a class that conforms to ObservableObject protocol. It has two @Published properties: fruitArray & isLoading. This viewmodel will be instantiated in the ViewModel struct. This FruitViewModel also controls the data flow between the View and the ViewModel. Then we have navigation link to the SecondScreen struct. Then, we pass the FruitViewModel to the SecondScreen struct. In the SecondScreen struct, we have a button to go back to the ViewModel struct. In the SecondScreen, this can access the FruitViewModel’s properties (which in this case, fruitArray mainly).

There are two ways to instantiate the FruitViewModel. One is using @StateObject and the other is using @ObservedObject. For @StateObject, it’s used for the object that is created by the View. For @ObservedObject, it’s used for the object that is shared across the app. This means you can still use @ObservedObject for the object that is created by the View, but if it’s observableobject, it’s not going to be persisted. meaning the data will be changed when the view is changed. So, it will change everytime the view is changed where this wouldn’t be our case. So, that’s why we use @StateObject to keep the data persistence.

class FruitViewModel : ObservableObject {
    @Published var fruitArray: [FruitModel] = [] // state in class (alert to ViewModel)
    @Published var isLoading: Bool = false
    
    init() {
        getFruits()
    }
    
    func getFruits() {
        let fruit1 = FruitModel(name: "Banana", count: 2)
        let fruit2 = FruitModel(name: "Watermelon", count: 9)
        
        isLoading = true
        DispatchQueue.main.asyncAfter(deadline: .now() + 3.0){
            self.fruitArray.append(fruit1)
            self.fruitArray.append(fruit2)
            self.isLoading = false
        }
    }
    
    func deleteFruit(index: IndexSet) {
        fruitArray.remove(atOffsets: index)
    }


struct ViewModel: View {
    @StateObject var fruitViewModel: FruitViewModel = FruitViewModel()
    
    var body: some View {
        NavigationView {
            List {
                if fruitViewModel.isLoading {
                    ProgressView()
                    
                } else {
                    ForEach(fruitViewModel.fruitArray) { fruit in
                        HStack {
                            Text("\(fruit.count)")
                                .foregroundColor(.red)
                            Text(fruit.name)
                                .font(.headline)
                                .bold()
                        }
                    }
                    .onDelete(perform: fruitViewModel.deleteFruit)
                }
            }
            .listStyle(.grouped)
            .navigationTitle("Fruit List")
            .navigationBarItems(
                trailing: NavigationLink(destination: SecondScreen(fruitViewModel: fruitViewModel), label: { Image(systemName: "arrow.right")
                    .font(.title)})
            )
        }
    }
}
}

struct SecondScreen : View {
    @Environment(\.presentationMode) var presentationMode
    @ObservedObject var fruitViewModel: FruitViewModel
    var body: some View {
        ZStack {
            Color.green.ignoresSafeArea()
            VStack {
                Button(action: {
                    presentationMode.wrappedValue.dismiss()
                }, label: {
                    Text("Go Back")
                        .foregroundColor(.white)
                        .font(.largeTitle)
                        .fontWeight(.semibold)
                })
                
                VStack {
                    ForEach(fruitViewModel.fruitArray) { fruit in
                        Text(fruit.name)
                            .foregroundColor(.white)
                            .font(.headline)
                    }
                }
            }
        }
    }
}

EnvironmentObject

EnvironmentObject is a bit same as @ObservedObject. The difference is that it’s used for the object that is shared across the app. This means you can still use @ObservedObject for the object that is created by the View, but if it’s observableobject, only the subview can access the data. But if you use EnvironmentObject, the data will be shared across the app. Obviously there is downside to this, which means it’s slower than @ObservedObject. So if we have a hierchical structure, we can use EnvironmentObject to share the data across the app. (if only needed). So that the child view can access the data from the parent view. Otherwise, you can easily use @ObservedObject and pass this to child view.

The example code is as below

//
//  EnvironmentObject.swift
//  SwiftfulThinking
//
//  Created by Seungho Jang on 2/25/25.
//

import SwiftUI

// What if all child view want to access the Parent  View Model.
// Then use EnvironmentObject.
// You can certainly do pass StateObject / ObservedObject, but what
// if you have a hierchy views want to access the parent views.
// but might be slow
class EnvironmentViewModel: ObservableObject {
    @Published var dataArray: [String] = []
    
    init() {
        getData()
    }
    
    func getData() {
        self.dataArray.append(contentsOf: ["iPhone", "AppleWatch", "iMAC", "iPad"])
    }
}

struct EnvironmentBootCampObject: View {
    @StateObject var viewModel: EnvironmentViewModel = EnvironmentViewModel()
    
    var body: some View {
        NavigationView {
            List {
                ForEach(viewModel.dataArray, id: \.self) { item in
                    NavigationLink(
                        destination: DetailView(selectedItem: item),
                        label: {
                            Text(item)
                        })
                }
            }
            .navigationTitle("iOS Devices")
        }
        .environmentObject(viewModel)
    }
}

struct DetailView : View {
    let selectedItem: String
    var body: some View {
        ZStack {
            Color.orange.ignoresSafeArea()
            
            NavigationLink(
                destination: FinalView(),
                label: {
                    Text(selectedItem)
                        .font(.headline)
                        .foregroundColor(.orange)
                        .padding()
                        .padding(.horizontal)
                        .background(Color.white)
                        .cornerRadius(30)
                })
        }
    }
}

struct FinalView: View {
    @EnvironmentObject var viewModel: EnvironmentViewModel
    var body: some View {
        ZStack {
            LinearGradient(gradient: Gradient(colors: [.blue, .red]),
                           startPoint: .topLeading,
                           endPoint: .bottomTrailing)
            .ignoresSafeArea()
            
            ScrollView {
                VStack(spacing: 20) {
                    ForEach(viewModel.dataArray, id: \.self) { item in
                        Text(item)
                    }
                }
            }
            .foregroundColor(.white)
            .font(.largeTitle)
        }
    }
}

At the end…

Why do we use StateObject & EnvironmentObject? It’s matter of the lifecycle of the object as well as the MVVM Architecture. The MVVM Architecture is a design pattern that separates the UI, the data, and the logic. The StateObject is used for the object that is created by the View. The EnvironmentObject is used for the object that is shared across the app.

Resource

바로 아래의 Diagram 을 살펴보자.

위의 그림을 보자면, Source Code 에서 nvcc (nvidia) CUDA Compiler 가 CUDA 관련된 코드만 쏙 빼가서, 그부분만 컴파일을 하게 된다. Compile 을 한 이후에, executable code 만 GPU 에게 넘겨준다. 즉 전에 Post 에서 사용했던 __global__ 코드만 nvcc 가 가로채서 GPU 에서 실행을 했다고 생각을 하면된다. 그리고 남은거는, MSVC 또는 GNU 가 pure C++ Code 만 가져가서, CPU 에 실행한다고 볼수 있다.

여기에서 용어를 한번 정리를 한다면 …

• CUDA Kernel: GPU 가 실행하는 작은(병렬) 프로그램
• VRAM: CUDA 가 사용하는 메모리

직접적인 I/O 는 오로지 South PCI Slot 이므로 North PCI 에서는 안됨, 그래서 간접적으로 해야한다. 즉 이 말은 I/O 에서 받아오는것들을 Main Memory 로 들고 온이후에, CUDA Memory (VRAM) 으로 Copy 를 해주면 된다. 그래서 이것저것 GPU 에서 한 이후에, Main Memory 로 다시 넘겨주면 되는 형식이다. 즉 다시 정리를 하자면

1. 외부 데이터로부터 메인메모리, 메인메모리부터 비디오 메모리 (Host CPU)
2. CUDA Kernel 실행, 비디오 메모리 데이터 사용, GPU 로 병렬처리, 처리 결과는 비디오 메모리 (Device=Kernel Program)
3. 비디오 메모리 -> 메인메모리, 외부로 보내거나, I/O 출력 (Host CPU)

이런식으로 3 단계로 일반적인 Step 이라고 볼수 있다.

Memory Handling

CPU 와 GPU 메모리는 공간이 분리되어있다는 걸 염두할 필요가 있다. 그리고 CPU 와 GPU 에서의 Memory 할당을 보자

메인메모리 할당/복사 C++ 함수 사용

void* malloc(size_t nBytes);
void free(void* ptr);
void* memset(void*ptr, int value, size_t count);
void* memcpy(void* dst, const void*src, size_t num);

Example:

int nbytes = 1024 * sizeof(int);
int *ptr = nullptr;
ptr = malloc(nbytes);
memset(ptr, 0, nbytes);
free(ptr);

비디오 메모리 할당/복사: 별도의 CUDA 함수 이용

cudaError_t cudaMalloc(void** dev_ptr, size_t nbytes);
cudaError_t cudaMemset(void* dev_ptr, int value, size_t count);
cudaError_t cudaFree(void* dev_ptr);
cudaError_t cudaMemcpy(void* dst, void* src, size_t nbytes, enum cudaMemcpyKind direction);

Example:

int nbytes = 1024 * sizeof(int);
int* dev_ptr = nullptr;
cudaMalloc((void**)&dev_ptr, nbytes);
cudaMemset(dev_ptr, 0, nbytes);
cudaFree(dev_ptr);

여기에서 cudaMemcpy 를 한번보자.

• 이전 CUDA 함수들이 모두 종료되어야 복사가 시작된다.
• copy 중에는 CPU Thread Pause, 작업이 완료되어야 리던한다.
• host = CPU, main memory, RAM
• device = CUDA, video memory, vram
• enum cudaMemcpyKind
  • cudaMemcpyHostToDevice
  • cudaMemcpyDeviceToHost
  • cudaMemcpyDeviceToDevice
  • cudaMemcpyHostToHost

특별 이슈라고 말을 할수 있는건 아래와 같다.

• Memory address 문제
• 어느쪽 주소인지 ㅣ프로그래머가 구별
• 반대쪽 Address 를 넣으면 System Crash 발생가능
• 해결책: device 에서는 dev_ 사용

예제를 한번 보자. 자세하게 보면, 메모리를 할당할때, 간접적으로, dev_a 와 dev_b 를 받아주는걸 볼수 있다. 그리고, Host 에서 GPU 로 a 라는 걸 SIZE * sizeof(float) 만큼 할당해서, device 에 있는 dev_a 를 가르키게끔 되어있다. 그다음 dev_b 에서 dev_a 를 copy 한 이후에, dev_b 에 있는걸 b 로 Copy 하는 걸 볼 수 있다.

#include <stdio.h>
#include <cuda.h>
#include <cuda_runtime_api.h>
#include <cuda_runtime.h>

int main()
{
    const int SIZE = 8;
    const float a[SIZE] = { 1., 2., 3., 4., 5., 6., 7., 8. }; //src
    float b[SIZE] = { 0., 0., 0., 0., 0., 0., 0., 0. }; //dst

    printf("a = {%f,%f,%f,%f,%f,%f,%f,%f}\n", a[0], a[1], a[2], a[3], a[4], a[5], a[6], a[7]);
    fflush(stdout);

    float* dev_a = nullptr;
    float* dev_b = nullptr;
    cudaMalloc((void**)&dev_a, SIZE * sizeof(float));
    cudaMalloc((void**)&dev_b, SIZE * sizeof(float));

    cudaMemcpy(dev_a, a, SIZE * sizeof(float), cudaMemcpyHostToDevice);
    cudaMemcpy(dev_b, dev_a, SIZE * sizeof(float), cudaMemcpyDeviceToDevice);
    cudaMemcpy(b, dev_b, SIZE * sizeof(float), cudaMemcpyDeviceToHost);

    cudaFree(dev_a);
    cudaFree(dev_b);

    printf("b = {%f,%f,%f,%f,%f,%f,%f,%f}\n", b[0], b[1], b[2], b[3], b[4], b[5], b[6], b[7]);
    fflush(stdout);
    return 0;
}

그렇다면, 코드 생성은 컴파일러 입장에서는, 어떤 코드는 CPU 로 가고, 어떤 코드는 GPU 로 가는지를 한 소스코드에서 판단을 해야한다. 즉 어디까지는 끊어서 이거는 내가 어디를 끊어야될지를 구분을 지어야한다. 방법으로틑 파일이 있다. 즉 어떤 파일은 CUDA 로 Compile 하게 끔, 다른 어떤 파일은 MSVC 로 Compile 하게끔 한다. 또 한줄씩 컴파일로 할때도 가능이 가능하다. 하지만 둘다 Bottleneck 이 존재한다. 파일로 할때는, 관리를 해줘야하며, 코드 라인으로 할때는 너무 하기에는 양이 너무 많다.

그래서 그 중간이 Function 이다 (어떠한 Cuda programming model 이라고 보면 좋을것 같다.) 즉 compilation unit 은 function 단위로 하게끔 되고, 각각의 function 들은 GPU 로 할지 CPU 로 할지가 결정된다! 어떻게 이걸 결정을 하느냐? 바로 PREFIX 이다. 즉 아래와 같이 어떤 컴파일러가 이 Function 을 가져갈지를 정한다.

Prefix 의 종류는 아래와같다.

• __host__ : can be called by CPU (default, can be omitted) (called by host, excuted on host)
• __device__: called from other GPU Functions, cannot be called by the CPU (called by device, executed on device)
• __global__: launched by CPU, cannot be called from GPU, must return void (called by host, executed on device)
• __host__ and __device__ qualifiers can be combined.

결국에 정리를 하자면, *__global__ defines kernel function

• each “__” consists of two underscore character

• A kernel function must return void

• __device__ and __host__ can be used together, which means compiled twice(!), both cannot have their address taken!!

그리고 Restriction 이 존재한다. CUDA Language = C/C++ language with some restriction: (즉 병렬처리를 위해서 Bottleneck 을 만든 현상)

• Can only access GPU Memory (CUDA memory, video memory)
  • in new versions, can access host memory directly, with performance drawback
  • No static Variables (No static variable declarations inside the function)
  • No recursion (it is possible in newer version)
  • No dynamic polymorphism

이렇게 해서, 일단 한단락을 마무리 지으려고 한다!

Resource

Courses

• CUDA 를 설치하기 위해서 해야하는것을 간단히 소개 하겠다. CUDA 를, 즉 개발 환경을 설정하려면 아래의 목록 대로 설치 할 필요가 있다.
  • Visual Studio 2019/2022
  • Nvida Graphic App
  • CUDA Toolkit (***)
  • Nsight Visual Studio Editon Extension in Visual Studio
  • Nsight System
  • Nsight Compute
  • vcpkg (C++ Library, like pip)
• vcpkg 에 필요한 라이브러리는 설명하지는 않겠다. 단 몇가지를 설치할 필요가 있다.

./vcpkg install vulkan:x64-windows, stb:x64-windows, glfw3:x64-windows, glm:x64-windows
./vcpkg install vulkan:x64-windows stb:x64-windows glfw3:x64-windows glm:x64-windows
./vcpkg install vulkan:x64-windows
./vcpkg install stb:x64-windows
./vcpkg install glfw3:x64-windows
./vcpkg install glm:x64-windows

CUDA: Hello World

위의 내용을 설치하지 않아도, cuda tool kit 이 설치가 완료 되었다고 한다고 하면, 굳이 할 필요 없다. Visual Studio 만으로도 충분히 사용할 수 있다. 일단 C 에 Program Files 안에 CUDA Toolkit 안에 있는 예제 .exe 파일을 돌려보거나, 설치가 되어있다고 하면, Project 를 생성할때 아래와 같이 사용할수 있다.

그리고, 코드를 보면 cu 라는 확장자를 가지고 있다. 또 아래의 코드처럼 생성 이후에, 실행을 시켜보면. hello, CUDA 가 출력이 된다. 자 여기서, 분명 __global__ void hello(void) 쪽이 바로 CUDA 에서 실행되는 부분이다. 그리고 __global__ 이라는 것은 이 함수가 GPU 에서 실행될 것이라는 것을 의미한다. 그리고 이 함수는 모든 GPU 에서 실행될 것이다. 즉 하나의 설정자이다. CUDA 라는게 C++ 위에 올라가는거기때문에, editor 에서 에러 처럼 보일수 있다.. 이건 c/c++ 이 CUDA Kernel 을 포함시킨다를 의미한다.

그리고 <<>> 이 부분이 1 x 1 즉 1 개 Core 만 사용한다는 뜻이다. (Liunux 에서는 안들어갈수 있다.) 저걸 만약에 «1 , 8» 이라고 하면, 1 x 8 개의 Core 를 동시에 사용한다는 의미이다. 그리고 만약 «8, 2» 라고 한다면, 16 개의 Core 를 동시에 사용한다는 의미이다. 그리고 8 개의 세트를 두번씩 돌린다는 말이다.

#include <cstdio>

__global__ void hello(void)
{
    printf("hello, CUDA\n");
}

#include <vector>
int main()
{
    hello << <1, 1 >> > (); // parallel execution (call cuda) 
    return 0;
}

OS 에 상관 없이 돌려 보아야하기 때문에, Linux 에서 사용을 해보도록 하자. Linux 에서 사용하려면, cudaDeviceSynchronize() 를 사용해야한다. 이 함수는 모든 thread 가 끝날때까지 기다리는 함수이다. 그래서 이 함수를 사용하면, 모든 thread 가 끝날때까지 기다리기 때문에, 모든 thread 가 끝나고 나서야 다음 코드를 실행할수 있다.

#include <cstdio>

__global__ void hello(void)
{
    printf("hello, CUDA %d\n", threadIdx.x);
}

#include <vector>
int main()
{
    hello << <1, 8>> > ();
    #if defined(__linux__)
        cudaDeviceSynchronize();
    #endif
    fflush(stdout);
    return 0;
}

Resource

Courses

React Native 시작 및 동기부여

사실 Interactive Web 을 사용하고 싶었고, 뭔가 항상 가지고 있었던, Front-end 는 별로야. 너무 볼것도 많고, 디자인 할것도 많고, Core Value 가 없어보여.. 이런말만 했었는데, 요즘은 Spatial Computing 이 되게 중요하지 않나? 라고 생각해서 mobile 로 할수 있는게 뭘까? 하니 What is Spatial Computing. 읽어보면,

It’s the purset form of “blending technology into the world

라고 작성이 되어있다. 즉 우리가 사용하는 Computer Hardware 를 사라지게 하며, digital 현상으로 볼수 있는, machine 으로 부터 Output 만 보는 형태! 라고 볼수 있다. Application 으로는 VR/AR/MR 등이 있으며, 아래와 같이 정의한다.

• VR: VR places the user in another location entirely. Whether that location is computer-generated or captured by video, it entirely occludes the user’s natural surroundings.

• AR: In augmented reality - like Google Glass or the Yelp app’s monocle feature on mobile devices - the visibile natural world is overlaid with a layer of digital content.

• MR: In technologies like Magic Leap’s virtual objects are integrated into - and responsive to- the natural world. A virtual ball under your desk, for example, would be blocked from view unless you bent down to look at it. In theory, MR could become VR in a dark room.

좋은 실무 예제로는 Youtube 이 있을것 같다.

Before getting into develop mode

일단 개발환경을 앞서서, 어떻게 XR 과 관련된 개발을 찾아보자. 일단 ARKit, RealityKit 같은 경우는 ARKit 은 증강현실 프레임워크 이고, RealityKit 는 3D Rendering Framework 이다. RealityKit 이 ARKit on top (ARSession) 에 실행된다고 보면 된다. RealityKit 은 rendering 할수 있는 engine 이 존재하고, physics 또는 animation 을 담당한다. 언어로는 swift / object-c 가 있다. 물론 Framework (Unity)를 껴서 개발은 가능하다. 더 자세한건 여기 Forum 에서 보면 될것 같다. 그리고 RealityKit 과 Metal Computing Shader 와는 같이 작동하고, API 를 사용해서 렌더링 성능을 향상 시킨다.

그리고 OpenXR 같은 경우 vulkan 을 만든 chronus group 에서 만들어졌고, 뭐 C/C++ 을 사용한다. 그리고 나머지는 WebXR 이다. 웹브라우저에서 XR 을 지원하기 위해서 만들어졌으며, WebGL 함께해서 갭라을 한다고 하자.

물론 Metal 을 공부하는것도 나쁘진 않지만, 기본적인 구조는 DirectX11/12 Graphics Pipeline 는 같은것 같다?(이건 확인 필요!)

Setting up IOS(VM) Dev on Windows or MacOS directly

이 부분은 굉장히 까다로웠다. 일단 기본적으로 환경설정을 고려할때, 굳이 macOS 를 Base 로 쓰고 싶지 않았다. VMWare 설치 및 환경설정 (단 여기서, .iso file 은 unlocker 에 있는 .iso) 파일을 설치하도록 하자. 그리고 Resolution Setting 여기를 확인해보자. 가끔씩 VMWare 가 금쪽이 같은 면 이있지만 App 을 Build 하고 코드 작성하는데 크게 문제가 있지는 않은것 같다. 그리고 XCode 를 혹시 모르니까 설치를 해놓자. 설치하는데 시간을 뻇기는건 어쩔수 없는거긴 하지만, 너무 비효율적이고, 길어진다. 인터넷 같은 경우에는 VMWare Player 세팅에서, NAT: Used to share the host's IP address 만 해놓으면 괜찮다.

그리고 부가적으로, Homebrew 를 설치하자. /bin/bash -c "$(curl -fsSL https://raw.githubusercontent.com/Homebrew/install/HEAD/install.sh)".

그이후에 https://reactnative.dev/docs/set-up-your-environment?os=macos&platform=ios 여기에서 Environment 를 설정해주자.

brew install node
brew install watchman
ruby - v
brew install rbenv
rbenv install -l
rbenv install {latest_version}  # check
rbenv global {latest_version}   # check
sudo gem install bundler

설치 되었다면 확인 하자!

node - v
nvm - v
npm - v

vim ~/.zprofile # or .zsrc / .bashrc

# add this into .zprofile & .zsrc & .bashrc
export NVM_DIR="$HOME/.nvm"
[ -s "/opt/homebrew/opt/nvm/nvm.sh" ] && \. "/opt/homebrew/opt/nvm/nvm.sh"  # This loads nvm
[ -s "/opt/homebrew/opt/nvm/etc/bash_completion.d/nvm" ] && \. "/opt/homebrew/opt/nvm/etc/bash_completion.d/nvm"  # This loads nvm bash_completion

source ~/.zprofile  # .zprofile, .zsrc, .bashrc

nvm install --lts
node - v
nvm - v
npm - v

이후에는 XCode 설치 및 설정을 한다. XCode -> Settings -> Command Line Tool 최신으로 바꿔준다. 그리고 IOS Simulator 를 설치하면 끝이다.

Project Setting

프로젝트 생성 관련 및 개발환경 관련된건 두가지가 있다. Expo 와 React Native CLI 가 있는데, 자세한건 이 링크 간단하게 말하면, Expo 는 개발 환경 초기설정을 단순화하고 개발 속도가 빠르다는 장점이 있다. Expo go 앱이 있다면 프로젝트 실행이 된다. 하지만 제공되는 API 만 사용해야되고 Native Module 이 없기 때문에, 기술 구현상 어려운 부분이 있다. 그리고 Package 볼때, Expo 에 사용될수 있는지 확인 해야 한다.

React Native 같은 경우 Native module 을 사용할수 있고, 다양한 라이브러리 사용 가능하다. 기본적으로 제공되는 라이브러리가 없다 보니, 대부분 기능 구현에 있어서는 직접 설치해야한다 하지만 장점으로는 유지보수가 잘되어있다고 한다. (이건 잘모름) 배포 하기 위해서는 Android Studio 나 XCode 가 있어야한다. 이 글을 보게 되면 어떤걸로 개발할지가 뭔가 잘 나와있다. 결국에는 요약한건 이거다. (React Native itself is an abstraction over the native layer and expo adds another abstraction on top of that one ... learning react native cli first can help you with debugging issues when using expo)

Create Project

처음 하기에는 expo 로 한다고 했는데, 나는 장기적으로 보기 때문에, cli 로 했다. expo 로 개발하려면 expo 개발환경 설정 참조하자.

기존에 react-native-cli 를 전역(global) 로 설치한적 이 있으면 깔끔하게 지워주자. 그리고 project 를 생성하자.

npm uninstall -g react-native-cli @react-native-community/cli
npx @react-native-community/cli@latest init {project_name}

의존설 설치 관련되서는 npm install 이나 yarn 을 설정하면 된다. 그 이후 cocoapod 를 설치 하면된다.

npm install
cd ios 
bundle exec pod install # or pod install

코드 서명하는법은 skip 하도록 하겠다. 그리고 yarn start 하고 i 를 누르거나 npx react-native run-ios 하면 아래와 같은 그림이 나올거다.

만약하다가 error code 65 가 나온다면 아래와 같이 해주자

rm -rf ~/Library/Developer/XCode/DerivedData`
sudo killall Simulator
rm -rf ~/Library/Developer/CoreSimulator/Cashes

그리고 아래와 같은 그림으로 나올거다. 주의점으로는 절대 빌드 할때 급하게 exit 하지 말자! 알아서 잘될거다.

이로 끝! 긴여정이 끝났다. 개발만 해보자!

Hello World

자 일단 크게 변경 할점은 App.tsx JSX 로 되어있는 부분에 function APP() 이부분을 수정을 하면 Hello World 를 볼수 있다.

더 자세한건 Integration with existing app 이걸 보면 될것 같다.

Resource

• Youtube
• What’s the difference or relationship between ARKit, RealityKit, SceneKit, QuickLook, and Reality Composer?
• Blog
• Blog
• How to develop app in Orion or Meta Quest3
• How to create a WebXR App using React
• Meta Spatial SDK
• React Three Fiber

Combine 을 알기전에…

Combine 을 알기전에 앞서서, Combine 이 나오기전에 어떻게 비동기 event 를 처리했는지 보자. 아래의 코드는 간단한 Fake Jason Data 를 Load 해서 UI 에 뿌리는 용도이다. @escaping 이라는걸 간단하게 이야기하자면, 일단 함수안에 completionHandler 가 매개상수로 들어오고, 이 closure 는 함수가 시작한 이후에 바로 실행시킬수 있게끔 되어있다. 만약 asyncAfter 를 사용하게 되면, 함수는 끝나는데 closure 가 살아있을수가 없기 때문에, @escaping 사용해서 closure 가 비동기로 사용할수 있게끔 만들어주는거다. 이를 통해서 비동기 처리를 통해서 Data 를 받아 올수 있었다.

import SwiftUI

struct PostModel: Identifiable, Codable {
    let userId: Int
    let id: Int
    let title: String
    let body: String
}

class DownloadwWithEscapingViewModel : ObservableObject {
    @Published var posts: [PostModel] = []
    init(){
        getPosts()
    }
    
    func getPosts(){
        guard let url = URL(string : "https://jsonplaceholder.typicode.com/posts") else { return }
        downloadData(fromURL: url) { (returnedData) in
            if let data = returnedData {
                guard let newPosts = try? JSONDecoder().decode([PostModel].self, from: data) else { return }
                DispatchQueue.main.async{ [weak self] in
                    self?.posts = newPosts
                }
            }
        }
    }
    
    func downloadData(fromURL url: URL, completionHandler: @escaping (_ data: Data?) -> Void) {
        URLSession.shared.dataTask(with: url) { (data, res, err) in
            guard
                let data = data,
                err == nil,
                let res = res as? HTTPURLResponse,
                res.statusCode >= 200 && res.statusCode < 300 else {
                print("No data.")
                completionHandler(nil)
                return
            }
            completionHandler(data)
        }.resume() // start
    }
}

struct DownloadWithEscapingBootcamp: View {
    @StateObject var vm = DownloadwWithEscapingViewModel()
    
    var body: some View {
        List {
            ForEach(vm.posts) { post in
                VStack(alignment: .leading){
                    Text(post.title)
                        .font(.headline)
                    Text(post.body)
                        .foregroundColor(.gray)
                }
                .frame(maxWidth: .infinity, alignment: .leading)
            }
        }
    }
}

#Preview {
    DownloadWithEscapingBootcamp()
}

Combine

애플 Dev 공식문서에 보면…

The Combine framework provides a declarative Swift API for processing values over time. These values can represent many kinds of asynchronous events. Combine declares publishers to expose values that can change over time, and subscribers to receive those values from the publishers.

즉 Publisher 와 Subscriber 가 있고, Publisher 는 Data 를 방출하거나, 뭔가의 완료의 Signal 보내는 역활을 하고, Subscriber 는 Publisher 가 쏴준 Data 나 완료 Signal 을 받는 역활을 한다. 그리고 그 사이에 Operator 가 있는데 Publisher 가 생성하는 이벤트를 처리하는 역활을 한다. 이때 연산자(map, filter, reduce) 를 사용할수 있다.

기본적인 예시는

import Combine

let publisher = [10, 20, 30, 40, 50].publisher 

publisher
    .map { $0 * 2 } // Operator 를 통해서 값 변환
    .sink { print($0) } // 값을 recevied

Publisher 연산자에도 (Just, Sequence, Future, Fail, Empty, Deferred, Record) 등이 있다. Just 를 사용한 Publisher 를 사용해보자.

import Combine
let justPublisher = Just(20)

justPublisher
    .map { $0 + 50 }
    .sink { print($0) }

아래의 코드는 여기에서 "https://jsonplaceholder.typicode.com/todos/1" todo 를 하나 가지고 와서, Data 를 Publisher 를 통해서 가지고 온이후에 subscriber 로 receive 받은 이후, UI 를 main thread 에서 update 를 해주는 코드이다.

struct PostModel: Identifiable, Codable {
    let title: String
}

class DownloadTodoViewModel : ObservableObject {
    @Published var todos: [PostModel] = []
    var cancellables = Set<AnyCancellable>()
    init() {
        getTodo()
    }

    func getTodo() {
        guard let url = URL(string: "https://jsonplaceholder.typicode.com/todos/1") else {return}

        URLSession.shared.dataTaskPublisher(for:url)
            .subscribe(on: DispatchQueue.global(qos: .background))
            .receive(on: DispatchQueue.main)
            .tryMap { (data, response) -> Data in
                guard let response = response as ? HTTPURLResponse,
                    response.statusCode >= 200 & response.statusCode < 300 else {
                        throw URLError(.badServerResponse)
                    }
                    return data
            }
            .decode(type: PostModel.self, decoder: JSONDecoder())
            .sink { (completion) in

            } receiveValue: { [weak self] (returnTodo) in 
                self?.todos.append(returnTodo)
            }
            .store(in: &cancellables)
    }
}

그리고 Timer Publisher 의 사용법을 하려고 한다. Timer Thread 의 on 은 어떤 RunLoop 에서 Timer 를 사용할지를 정해줄수 있다. 여기에서는 main thread 를 사용하고, 어떠한 방식으로 RunLoop 을 실행할건지를 넣어주는데 default 값을 넣어주었다. 여기에서 필수적으로 알아야하는건 Timer 가 반환하는 Publisher 는 ConnectablePublisher 이며, 이 Publisher 를 subscribe 해서 실행하려면, connect() 나 autoconnect() 를 사용(첫 subscriber 구독 할때). sink 로 receive 해서 print 를 하면된다. 그리고 main thread 가 기다리면서, 5 초 뒤에 subscribe 취소 해주면된다.

import Combine

let timer = Timer.publish(every: 1.0, on: .main, in: .common).autoconnect()
var cancellable: AnyCancellable?

cancellable = timer
    .sink { print($0) }

DispatchQueue.main.asyncAfter(deadline: .now() + 5) {
    cancellable?.cancel()
}

Resource

• Blogs
• Youtube - Combine