Parallelization of Utility Programs
Based on Behavior Phase Analysis
Xipeng Shen

Chen Ding

Department of Computer Science
University of Rochester

1Motivation
Multi-core is coming to personal computers Many programs, especially those run on
past personal computers, are sequentialprograms
 Automatic parallelization is the path ofleast resistance2

Utility Programs
A class of dynamic programs which takea group of requests and serve them one
by one Examples
Compilers, interpreters, compressions,transcoding utilities, ...
GNU C compiler (Gcc)
The compilation of a function is a phase3

Challenges
Dynamic data (access)Dynamically allocated data structures
 One or more levels of indirections
Complex control flow
Input-dependent execution paths
 Many (recursive) function callsMore difficult to analyze and parallelize
than scientific programs
4

Opportunities
Different phase instances operate on
different data, thus have few data
dependences between them
 Recently we found a way to detect thephase boundaries
 Can we automatically parallelize those
programs at the phase level?
5Overview
Objective: to preliminarily check the feasibilityof parallelizing utility programs at phase level
without special hardware support
 Technology

Phase detection
 Dependence detection
 Program transformation

Evaluation
 Summary

6Behavior Phase Detection

Key idea: active profiling
Use regular input to trigger repetitive
behavior Filtering dynamic basic block trace basedon frequency and recurring distance Use real input to verify phase boundaries*Refer to “Shen et. al., TR 848, CS, U of Rochester, 2004”7

Phase-based Parallelization
Process-based parallelization
Separate address space

Each process executes one or a groupof phase instances

8Phase-Dependence Detection
Trace memory accesses in profiling runs
 Detect different kinds of dependences

anti- and output dependences can beignored because of separate address space Classify flow dependences into removableand non-removable types9

Flow Dependence

Removable flow dependence
Memory reuses Implicit initialization
 Byte operations


10

Memory Reuses
Two objects are allocated to the same
memory location in different part of theexecution.

11

Implicit Initialization
NODE* xlevel(NODE* expr){if (++xltrace<TDEPTH){...
}- - xltrace;}*code fragments from SPEC2K/LI
12

Byte Operation
char * buf;...
buf[i] = 0; // byte operation
lda s4, -28416(gp) // load array base address
addq s4, s0, s4 // shift to the target array element
ldq u v0, 0(s4) // load a quadword from the current element
mskbl v0, s4, v0 // set the target byte to 0 by masking
stq u v0, 0(s4) // store the new quadword to the array*code fragments from SPEC2K/Parser13

Program Transformation
We parallelize programs by hand at phaseboundaries based on the information
provided by the automatic tool
 A fully automatic tool would include
automatic parallelization with run-time
support to guarantee correctness and rollback
when necessaryCurrently being studied

14

Evaluation (4-CPU Xeon 2GHz)
Gzip

Parser2

4

Speedup times

1.5
10.5
0-0.5

18

Process Number

15

Speedup times

Evaluation (16-CPU Sunfire
Sparc V9 1.2 GHz)
Gzip

Parser

4814
12
10864
20121632

Process Number

16SummaryA preliminary exploration on the coarsegrain parallelization of utility programs
based on behavior phases
 Fully automatic system remains ourfuture work

17

TheEndThanks!

18