Sergey Pupyrev

Dr. Sergey Pupyrev


Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 March 2020 in Algorithmica
Verified
Journal Article
Open access
PDF file
JAJawaherul Md. Alam
Jawaherul Md. Alam
MBMichael A. Bekos
Michael A. Bekos
MGMartin Gronemann
Martin Gronemann
MKMichael Kaufmann
Michael Kaufmann
SPSergey Pupyrev
Sergey Pupyrev
A queue layout of a graph G consists of a linear order of the vertices of G and a partition of the edges of G into queues, so that no two independent edges of the same queue are nested. The queue number of graph G is defined as the minimum number of queues required by any queue layout of G. In this paper, we continue the study of the queue number of planar 3-trees, which form a well-studied subclass of planar graphs. Prior to this work, it was known that the queue number of planar 3-trees is at most seven. In this work, we improve this upper bound to five. We also show that there exist planar 3-trees whose queue number is at least four. Notably, this is the first example of a planar graph with queue number greater than three.

21 January 2018
Verified
Book Chapter
Closed access
PDF file
SPSergey Pupyrev
Sergey Pupyrev

1 January 2020
Verified
Book Chapter
Open access
PDF file
HPHelen C. Purchase
Helen C. Purchase
DADaniel Archambault
Daniel Archambault
SKStephen Kobourov
Stephen Kobourov
MNMartin Nöllenburg
Martin Nöllenburg
SPSergey Pupyrev
Sergey Pupyrev
HWHsiang-Yun Wu
Hsiang-Yun Wu
Do algorithms for drawing graphs pass the Turing Test? That is, are their outputs indistinguishable from graphs drawn by humans? We address this question through a human-centred experiment, focusing on ‘small’ graphs, of a size for which it would be reasonable for someone to choose to draw the graph manually. Overall, we find that hand-drawn layouts can be distinguished from those generated by graph drawing algorithms, although this is not always the case for graphs drawn by force-directed or multi-dimensional scaling algorithms, making these good candidates for Turing Test success. We show that, in general, hand-drawn graphs are judged to be of higher quality than automatically generated ones, although this result varies with graph size and algorithm.

30 March 2020 in IEEE Transactions on Computers
Verified
Journal Article
Closed access
ANAndy Newell
Andy Newell
SPSergey Pupyrev
Sergey Pupyrev
Basic block reordering is an important step for profile-guided binary optimization. The state-of-the-art for basic block reordering is to maximize the number of fall-through branches. However, we demonstrate that such orderings may impose suboptimal performance on instruction and I-TLB caches. We propose a new algorithm that relies on a model combining the effects of fall-through and caching behavior. As details of modern processor caching is quite complex and often unknown, we show how to use machine learning in selecting parameters that best trade off different caching effects to maximize binary performance. An extensive evaluation on a variety of applications, including Facebook production workloads, the open-source compilers Clang and GCC, and SPEC CPU benchmarks, indicate that the new method outperforms existing block reordering techniques, improving the resulting performance of applications with large code size. We have open sourced the code of the new algorithm as a part of a post-link binary optimization tool, BOLT.

1 March 2021 in Theoretical Computer Science
Verified
Journal Article
Closed access
JAJawaherul Md. Alam
Jawaherul Md. Alam
MBMichael A. Bekos
Michael A. Bekos
VDVida Dujmović
Vida Dujmović
MGMartin Gronemann
Martin Gronemann
MKMichael Kaufmann
Michael Kaufmann
SPSergey Pupyrev
Sergey Pupyrev

8 December 2016
Verified
Book Chapter
Closed access
PDF file
JAJawaherul Alam
Jawaherul Alam
MFMartin Fink
Martin Fink
SPSergey Pupyrev
Sergey Pupyrev