Source author record

Ching-Chi Lin

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Catalog footprint

Research overview

4works
3topics
4close collaborators

Published work

4 publications

preprint2023arXiv

HEP-BNN: A Framework for Finding Low-Latency Execution Configurations of BNNs on Heterogeneous Multiprocessor Platforms

Binarized Neural Networks (BNNs) significantly reduce the computation and memory demands with binarized weights and activations compared to full-precision NNs. Executing a layer in a BNN on different devices of a heterogeneous multiprocessor platform consisting of CPU and GPU can affect the inference performance, i.e., accuracy and latency. Usually, a heterogeneous HW platform consisting of a CPU and a GPU is available to execute the BNN workloads. However, to use the heterogeneous HW effectively, it is necessary to find an efficient strategy for BNN workload mapping. In this work, we propose a framework that generates efficient BNN layer-to-device mappings (i.e. suitable parallel configuration for each layer of the model) for execution platforms comprised of CPU and CUDA-capable GPU. We evaluate our proposed framework with two BNN architectures using two well-known datasets, Fashion-MNIST and CIFAR-10, on three hardware platforms with different characteristics. The results show that compared to running a fully-parallelized GPU implementation, our framework generates an efficient configuration up to 2x, 2.6x and 11.8x faster on our tested hardware respectively.

preprint2016arXiv

A Linear-Time Algorithm for the Weighted Paired-Domination Problem on Block Graphs

In a graph G=(V,E)G = (V,E), a vertex subset S⊆V(G)S\subseteq V(G) is said to be a dominating set of GG if every vertex not in SS is adjacent to a vertex in SS. A dominating set SS of GG is called a paired-dominating set of GG if the induced subgraph G[S]G[S] contains a perfect matching. In this paper, we propose an O(n+m)O(n+m)-time algorithm for the weighted paired-domination problem on block graphs using dynamic programming, which strengthens the results in [Theoret. Comput. Sci., 410(47--49):5063--5071, 2009] and [J. Comb. Optim., 19(4):457--470, 2010]. Moreover, the algorithm can be completed in O(n)O(n) time if the block-cut-vertex structure of GG is given.

preprint2014arXiv

Linear-Time Algorithms for the Paired-Domination Problem in Interval Graphs and Circular-Arc Graphs

In a graph GG, a vertex subset S⊆V(G)S\subseteq V(G) is said to be a dominating set of GG if every vertex not in SS is adjacent to a vertex in SS. A dominating set SS of a graph GG is called a paired-dominating set if the induced subgraph G[S]G[S] contains a perfect matching. The paired-domination problem involves finding a smallest paired-dominating set of GG. Given an intersection model of an interval graph GG with sorted endpoints, Cheng et al. designed an O(m+n)O(m+n)-time algorithm for interval graphs and an O(m(m+n))O(m(m+n))-time algorithm for circular-arc graphs. In this paper, to solve the paired-domination problem in interval graphs, we propose an O(n)O(n)-time algorithm that searches for a minimum paired-dominating set of GG incrementally in a greedy manner. Then, we extend the results to design an algorithm for circular-arc graphs that also runs in O(n)O(n) time.

preprint2002arXiv

Orderly Spanning Trees with Applications

We introduce and study the {\em orderly spanning trees} of plane graphs. This algorithmic tool generalizes {\em canonical orderings}, which exist only for triconnected plane graphs. Although not every plane graph admits an orderly spanning tree, we provide an algorithm to compute an {\em orderly pair} for any connected planar graph GG, consisting of a plane graph HH of GG, and an orderly spanning tree of HH. We also present several applications of orderly spanning trees: (1) a new constructive proof for Schnyder's Realizer Theorem, (2) the first area-optimal 2-visibility drawing of GG, and (3) the best known encodings of GG with O(1)-time query support. All algorithms in this paper run in linear time.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.