The whole computer hardware industry embraced the multi-core. The extreme optimisation of sequential algorithms is then no longer sufficient to squeeze the real machine power, which can be only exploited via thread-level parallelism. Decision tree algorithms exhibit natural concurrency that makes them suitable to be parallelised. This paper presents an in-depth study of the parallelisation of an implementation of the C4.5 algorithm for multi-core architectures. We characterise elapsed time lower bounds for the forms of parallelisations adopted and achieve close to optimal performance. Our implementation is based on the FastFlow parallel programming environment, and it requires minimal changes to the original sequential code.

Decision tree building on multi-core using FastFlow

ALDINUCCI, MARCO;
2014-01-01

Abstract

The whole computer hardware industry embraced the multi-core. The extreme optimisation of sequential algorithms is then no longer sufficient to squeeze the real machine power, which can be only exploited via thread-level parallelism. Decision tree algorithms exhibit natural concurrency that makes them suitable to be parallelised. This paper presents an in-depth study of the parallelisation of an implementation of the C4.5 algorithm for multi-core architectures. We characterise elapsed time lower bounds for the forms of parallelisations adopted and achieve close to optimal performance. Our implementation is based on the FastFlow parallel programming environment, and it requires minimal changes to the original sequential code.
2014
26
3
800
820
C4.5; Decision trees; Multi-core; Parallel classification
Marco Aldinucci; Salvatore Ruggieri; Massimo Torquati
File in questo prodotto:
File Dimensione Formato  
yadtff-j.pdf

Accesso aperto

Descrizione: post-print autore
Tipo di file: POSTPRINT (VERSIONE FINALE DELL’AUTORE)
Dimensione 892.9 kB
Formato Adobe PDF
892.9 kB Adobe PDF Visualizza/Apri
Aldinucci_et_al-2014-Concurrency_and_Computation__Practice_and_Experience.pdf

Accesso riservato

Descrizione: Editoriale
Tipo di file: PDF EDITORIALE
Dimensione 1.99 MB
Formato Adobe PDF
1.99 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/2318/139522
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 5
social impact