6.896 Project Presentations

Improving Cilk

Adaptively Parallel Processor Allocation for Cilk Jobs

Goal

Goal (cont.)

Illustration of Problem

Main Algorithmic Questions

Assumptions

References

Fast Serial-Append for Cilk

Serial-Append (cont'd)

Serial-Append (cont'd)

Serial-Append (cont'd)

Serial-Append

Project Goals

References

A Space-Efficient Global Scheduler for Cilk

Idea

AsyncDF Scheduler

Example

Comparison to Cilk

AsyncDF Optmizations

Project Plan

Questions?

Automatic conversion of NSP DAGs to SP DAGs

"Objectives :"

Transactional Cilk

Language-Level Complex Transactions
 C. Scott Ananian

An Evaluation of Nested Transactions

Transactional Memory

Nested Transactions

Concurrency

Nested Concurrent Transactions

Compiler Support for Atomic Transactions in Cilk

Determinacy Race Example

New Keywords in Cilk

Simulation of Transactional Memory

Work Involved

Data Race in Transactional Cilk

Background

Cilk’s transaction everywhere

Data Race

Non-Determinacy Detection

Linear-time determinacy race detection

Motivation

New algorithm for determinacy-race detection

The algorithm

Depth-first, left-to-right execution

Right-to-left execution

How to maintain both orders in serial execution

Example

Project Proposal:

Parallel Nondeterminator

Objective

Primitive Idea in Concurrency Test

"Two sets:"

"Sync:"

Primitive Idea for Access History

"Thank you very much!"

Parallel Nondeterminator
Wang Junqing

Using Cilk

Accelerating Multiprocessor Simulation

Introduction

The Meta Directory

Meta-directory example

Challenges

Methodology

Conclusion

Project Proposal: Parallelizing METIS

What is METIS?

Stages of Algorithm: Coarsening

Stages of Algorithm: Initial partitioning.

Stages of Algorithm: Uncoarsening and Refinement

Parallel Sorting
Paul Youn

Goals

HELP!

PROJECT PROPOSAL
SMA5509
Implement FIR filter in parallel computing using Cilk

Discrete Signal

FIR filter

Methods to process

b. Direct Form

The length of the input signal x(n) is L

The length of output y(n) will be L_y = L_x+L_h-1

c. Matrix form







with the dimension of H is

"Overlap-Add Block Convolution Method"

"2."

"Goal of project"

"How to implement"

Other things

Cache-Oblivious Algorithms

SMA5509: Theory of Parallel Systems

bzip2 compression

Burrows-Wheeler Transform (1994)

Why make it cache-oblivious?

Project Plan

New Cache-Oblivious Algorithms
Zhang Jiahui and Neel Kamal

Cache-Oblivious Lock Free Algorithms

Cache-Oblivious Algorithms

Packed Memory Structure

B-tree