NSD Schedule 2021 Autumn NYCU

Link to NYCU course system.

Week

Date

Subject

Comments

1

9/13 online (butter)

Introduction and Unit 1: Fundamental Engineering

hw #1

2

9/20

No meeting (mid-autumn holiday)

3

9/27 online (butter)

Unit 2: Python and Numpy

proposal

4

10/4 online (zoom)

Unit 3: C++ and Computer Architecture

hw #2

5

10/11

No meeting (national day)

6

10/18 online (zoom)

Unit 4: Matrix Operations

7

10/25

Unit 5: Cache Optimization

hw #3

8

11/1

Unit 6: SIMD (Vector Processing)

proposal due

9

11/8

Mid-term examination

10

11/15

Unit 7: Memory Management

hw #4

11

11/22

Unit 8: Ownership and Smart Pointers

12

11/29

Unit 9: Modern C++

hw #5

13

12/6

Unit 10: C++ and C for Python

14

12/13

Unit 11: Array Code in C++

hw #6

15

12/20

Unit 12: Advanced Python

16

12/27

Project presentation 1

17

1/3

Project presentation 2

18

1/10

Project presentation 3

Term Project

The course requires students to develop a software projects of a hybrid system of C++11 (modern C++) and Python for a numerical, scientific, or engineering problem. Everyone needs to individually write a proposal, develop the code, and present the project to the class at the end of the course. The grading guidelines are described in Practical Project.

The software needs to be open-source, hosted on github.com, and executable on Ubuntu 20.04 LTS on 64-bit x86 through command line. Building the software should use a single command.

The project proposal should be submit through the homework repository on time. A template can be found at General Proposal Template. The following contents should be included:

  1. Basic information (including the GitHub repository)

  2. Problem to solve

  3. Perspective users

  4. System architecture

  5. API description

  6. Engineering infrastructure

  7. Schedule

The proposal works like a specification, of which the purpose is to enable discussions that cannot be done with programming language. For example, source code is not suitable for describing software architecture. In The Architecture of Open Source Applications, you can see the many different ways that the developers use to present architecture. It is usually effective to use diagrams and natural language to do it.

With your proposal, I can help you manage the development through discussions (at which you should be pro-active). A plan will not be be 100% accurate and you should modify it as you go. Use pull requests to keep the proposal up-to-date.

You should write prototype code for your project while writing the proposal. The initial work will help you understand more about what to do. It is difficult, if not impossible, to write a proposal without prototyping.

There are some possible directions listed in this page. All of them are useful in a code name modmesh. Students are free to derive a subject from them, or come up with one by themselves.

Contiguous Array

N-dimensional arrays of fundamental types and struct are a building block for numerical code. It may be as simple as a pointer to a contiguous memory buffer, or well-designed meta-data with the memory buffer.

In modmesh, there is a class template SimpleArray implementing an N-dimensional array of contiguous memory. It is still in an early stage of development and may use a lot of enhancements.

A sample project proposal in this direction can be found in SimpleArray for Multi-Dimensional Field (a Sample Project Proposal).

Columnar Array

The Apache Arrow project provides a clear definition to the columnar data. Columnar data are an application of contiguous buffer, and provide a way to store flexible data format while providing high performance.

Because it is based on contiguous buffer, it is slow in insertion and resizing. But on the other hand, it provides constant-time random access and is friendly to cache optimization and SIMD (vector processing).

Graph Partitioning

Numerical solution of partial differential equations (PDEs) depends on discretization of space. The entities describing the discretized space is called mesh or grid. The mesh can be broadly categorized into structured and unstructured mesh. The latter is more flexible than the former.

The unstructured mesh allows free connectivity, which enables flexible distribution of data for parallel computing. The connectivity between mesh elements can be represented as a graph for partitioning. The graph-partitioning problem is useful to minimizing the communication between sub-mesh. There have been codes developed for this, e.g., METIS, and SCOTCH.

Boolean Operations on Polygons

In Euclidean space we are interested in finding the Boolean, i.e., AND, OR, NOT, XOR, of polygons. The polygonal Boolean operations are useful when we want to extract geometrical properties of the graphics. In two-dimensional space we deal with polygons. In three-dimensional space it is polyhedra. The Boolean operations are most useful in the two-dimensional space.

R-Tree Search Engine

R-tree is an index to speed up searches in space. It is usually referred to as a spatial index or just a tree. Data structures of the similar purpose include k-d tree, quadtree, etc. There is an R-tree implementation in boost.

Voronoi Diagram

The Voronoi diagram is a decomposition of a region that any point in a sub-region is closest to the site of the sub-region. This problem is useful when we are interested in distance to some sites in an Euclidean space. For example, we can use the Voronoi diagram to estimate the service areas of each branch of a reseller chain.

The Voronoi diagram will also be used to create triangular mesh in the Delaunay triangulation.