Talks by Faculties of Yonsei University

==============================================================================
                        Joint Seminars
==============================================================================
Speakers:       Faculties of Yonsei University, Korea

Title:          "Talks by Faculties of Yonsei University"

Date:           Thursday, 28 February, 2013

Time:           4:00pm - 5:30pm

Venue:          Room2612A (via lifts 31/32)
==============================================================================

1.      "YONSEI CS introduction talk"
         by Prof. Kyoungwoo LEE

2.      "An Improved Prefix-Free Regular-Expression Matching"
         by  Dr. Yo-Sub HAN

Abstract:

The regular-expression matching problem is an extension of the pattern
matching problem, for which a pattern is given as a regular expression. We
revisit the regular-expression matching problem with respect to
prefix-freeness of the pattern. It is known that a prefix-free pattern
gives only a linear number of matching substrings in the size of an input
text whereas there are a quadratic number of matching substrings for
general regular expressions. We improve the previous algorithm and suggest
an efficient algorithm that finds all pairs (start, end) of start and end
positions of all matching substrings with a single scan of the input when
the pattern is a prefix-free regular expression.


3.      "Orchestration by approximation: mapping stream programs onto
         multicore architectures"
         by Dr. Bernd BURGSTALLER

Abstract:

We present a novel 2-approximation algorithm for deploying stream graphs
on multicore computers and a stream graph transformation that eliminates
bottlenecks. The key technical insight is a data rate transfer model that
enables the computation of a "closed form", i.e., the data rate transfer
function of an actor depending on the arrival rate of the stream program.
A combinatorial optimization problem uses the closed form to maximize the
throughput of the stream program. Although the problem is inherently
NP-hard, we present an efficient and effective 2-approximation algorithm
that provides a lower bound on the quality of the solution. We introduce a
transformation that uses the closed form to identify and eliminate
bottlenecks.

We show experimentally that state-of-the art integer linear programming
approaches for orchestrating stream graphs are (1) intractable or at least
impractical for larger stream graphs and larger number of processors and
(2) our 2-approximation algorithm is highly efficient and its results are
close to the optimal solution for a standard set of StreamIt benchmark
programs.


************************
Biography:

Yo-Sub HAN

Yo-Sub HAN obtained his Ph.D. in computer science from HKUST in 2006. He
worked as a senior researcher in Korea Institute of Science and Technology
until 2009 and is currently an assistant professor at the department of
Computer Science at Yonsei University. His research interests include
formal language theory, algorithm design and information retrieval.



Bernd BURGSTALLER

Bernd BURGSTALLER is an Assistant Professor at the Department of Computer
Science at Yonsei University. He completed his PhD in static program
analysis at the Vienna University of Technology in 2005 and continued as a
postdoc at the University of Sydney until 2007. Before pursuing an
academic career, Bernd BURGSTALLEr worked in industry as programmer and
software architect for Philips Consumer Electronics, Vienna.