Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Porting PARSEC parallel benchmarks to taskcentric programming models: Improving the performance of the Content-Aware Similarity Search system (CASS) in the Ferret-toolkit
KTH, School of Information and Communication Technology (ICT).
KTH, School of Information and Communication Technology (ICT).
2013 (English)Independent thesis Basic level (professional degree), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

The Princeton Application Repository for Shared-Memory Computers (PARSEC) is a benchmarking suite constructed with multithreaded programs in mind. The suite mainly focus on testing chip-multicoreprocessors and how they perform emerging workloads1.

One of the workloads in PARSEC is Ferret which represents a content aware similarity search (CASS). There are  aws in the workload, mainly load imbalance and Input/Output(I/O)-bottlenecks which limits the performance. In this study the goal is to improve the Ferret-toolkit by making it task-parallel with Intel Cilk Plus and without changing the structure of the program. Task-parallelism achieves a better load balance and often results in better performance. The expectation were that the performance of Ferrets would increase.

The porting of the Ferret-toolkit wasn't successful. Many different approaches have been taken to achieve a task-centric version but none resulted in a fully functioning program. In some cases the program would work with certain input sizes and number of threads.

The main reason why the porting of Ferret wasn't possible is because of two large difficulties, input size and the structure of the whole program. The Ferret program is constructed as a parallel pipeline paradigm with six stages. Since every stage in the pipeline is dependent on the previous one a lot of dependencies had to be dealt with. It's difficult to program taskcentric models with dependencies since tasks aren't really supposed to handle dependencies and execute tasks in specific order.

The problem with input size is that the amount is unknown until the program have finished executing the first pipeline stage. This makes it hard to know how the granularity2 should be set, in which way to divide threads and how many tasks to create.

To get a fully functional task-parallel version of Ferret the whole structure have to be changed. The are to many dependencies and structural problems which can't properly be solved without changing the program radically. An alternative is to use an API which has better support for pipeline structures, such as Intel TBB.

Abstract [sv]

Princeton Application Repository for Shared-Memory Computers (PARSEC) är en s.k benchmarking3 svit byggd med multi-trådade program som fokus. Huvudsyftet med sviten är att testa hur flerkärninga processorerenheter presterar vid nya typer av mjukvara och arbetsuppgifter.

En av programmen i PARSEC är Ferret som representarar en content aware similarity search (CASS)4. Ferret har en del brister, huvudsakligen ojämn arbetsbörda mellan trådarna i programmet (s.k load imbalance) och flaskhalsar vid in- och utdatan i programmet.

Målet med detta arbetet är att förbättra Ferret genom att göra programmet task-parallelt m.h.a Intel Cilk Plus och utan att förändra programmets struktur. Task-parallelism skapar generellt jämnare arbetsbörda mellan trådarna (load balance) och bättre prestanda.

Modifieringen av Ferret lyckades dock inte: Många olika försök gjordes under arbetets gång för att få en task-parallel model men inget resulterade i ett fungerande program.I några fall har olika lösningsförslag reulterat i program som går att exekvera under vissa förutsättningar. T.ex. har några verisioner kunnat exekvera med ett visst antal trådar eller specifik storlek på indatan.

De största anledningarna till att Ferret inte lyckades göras task-parallelt är p.g.a programmets struktur och den okända mängden indata. Ferrets kod är strukturerad i en pipeline model med sex steg. Eftersom varje steg är beroende av det föregeånde behövs stora mängder av beroenden mellan stegen lösas. Task-parallel programering kan nämligen inte hantera beroenden mellan olika upgifter (tasks) på ett optimalt sett.

Problemet med indatans storlek är att den okänd fram tills det första pipeline steget har exekverat klart. Det är därför svårt att avgöra storleken på varje task (granularity), hur många tasks som ska skapas och hur trådarna ska delas upp mellan stegen.

För att skappa en helt fungerande task-parallel verision av Ferret måste stora delar av strukturen ändras. Många beroenden och strukturella problem i koden går inte att lösa utan att förändra programmets struktur radikalt. Ett annat alternativ är att använda ett task-parallelt API som stödjer pipeline parallelism, t.ex. Intel TBB.

Place, publisher, year, edition, pages
2013. , 44 p.
Series
TRITA-ICT-EX, 2013:156
Keyword [en]
PARSEC, Ferret, porting, pipeline, task-centric.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:kth:diva-177860OAI: oai:DiVA.org:kth-177860DiVA: diva2:874594
Examiners
Available from: 2015-12-01 Created: 2015-11-27 Last updated: 2015-12-01Bibliographically approved

Open Access in DiVA

No full text

By organisation
School of Information and Communication Technology (ICT)
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

urn-nbn

Altmetric score

urn-nbn
Total: 59 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf