FPGA-based architecture for computing testors

Alejandro Rojas, René Cumplido, J. Ariel Carrasco-Ochoa, Claudia Feregrino, J. Francisco Martinez-Trinidad

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearch

5 Citations (Scopus)

Abstract

Irreducible testors (also named typical testors) are a useful tool for feature selection in supervised classification problems with mixed incomplete data. However, the complexity of computing all irreducible testors of a training matrix has an exponential growth with respect to the number of columns in the matrix. For this reason different approaches like heuristic algorithms, parallel and distributed processing, have been developed. In this paper, we present the design and implementation of a custom architecture for BT algorithm, which allows computing testors from a given input matrix. The architectural design is based on a parallel approach that is suitable for high populated input matrixes. The architecture has been designed to deal with parallel processing of all matrix rows, automatic candidate generation, and can be configured for any size of matrix. The architecture is able to evaluate whether a feature subset is a testor of the matrix and to calculate the next candidate to be evaluated, in a single clock cycle. The architecture has been implemented on a Field Programmable Gate Array (FPGA) device. Results show that it provides significant performance improvements over a previously reported hardware implementation. Implementation results are presented and discussed. © Springer-Verlag Berlin Heidelberg 2007.
Original languageAmerican English
Title of host publicationFPGA-based architecture for computing testors
Pages188-197
Number of pages168
ISBN (Electronic)9783540772255
StatePublished - 1 Dec 2007
Externally publishedYes
EventLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) -
Duration: 1 Jan 2014 → …

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4881 LNCS
ISSN (Print)0302-9743

Conference

ConferenceLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Period1/01/14 → …

Fingerprint

Field Programmable Gate Array
Field programmable gate arrays (FPGA)
Computing
Parallel Processing
Mixed Data
Architectural Design
Distributed Processing
Supervised Classification
Architectural design
Incomplete Data
Hardware Implementation
Exponential Growth
Heuristic algorithms
Processing
Architecture
Classification Problems
Heuristic algorithm
Feature Selection
Feature extraction
Clocks

Cite this

Rojas, A., Cumplido, R., Carrasco-Ochoa, J. A., Feregrino, C., & Martinez-Trinidad, J. F. (2007). FPGA-based architecture for computing testors. In FPGA-based architecture for computing testors (pp. 188-197). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4881 LNCS).
Rojas, Alejandro ; Cumplido, René ; Carrasco-Ochoa, J. Ariel ; Feregrino, Claudia ; Martinez-Trinidad, J. Francisco. / FPGA-based architecture for computing testors. FPGA-based architecture for computing testors. 2007. pp. 188-197 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{1b29465276c34693930d537e9f4f963b,
title = "FPGA-based architecture for computing testors",
abstract = "Irreducible testors (also named typical testors) are a useful tool for feature selection in supervised classification problems with mixed incomplete data. However, the complexity of computing all irreducible testors of a training matrix has an exponential growth with respect to the number of columns in the matrix. For this reason different approaches like heuristic algorithms, parallel and distributed processing, have been developed. In this paper, we present the design and implementation of a custom architecture for BT algorithm, which allows computing testors from a given input matrix. The architectural design is based on a parallel approach that is suitable for high populated input matrixes. The architecture has been designed to deal with parallel processing of all matrix rows, automatic candidate generation, and can be configured for any size of matrix. The architecture is able to evaluate whether a feature subset is a testor of the matrix and to calculate the next candidate to be evaluated, in a single clock cycle. The architecture has been implemented on a Field Programmable Gate Array (FPGA) device. Results show that it provides significant performance improvements over a previously reported hardware implementation. Implementation results are presented and discussed. {\circledC} Springer-Verlag Berlin Heidelberg 2007.",
author = "Alejandro Rojas and Ren{\'e} Cumplido and Carrasco-Ochoa, {J. Ariel} and Claudia Feregrino and Martinez-Trinidad, {J. Francisco}",
year = "2007",
month = "12",
day = "1",
language = "American English",
isbn = "9783540772255",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "188--197",
booktitle = "FPGA-based architecture for computing testors",

}

Rojas, A, Cumplido, R, Carrasco-Ochoa, JA, Feregrino, C & Martinez-Trinidad, JF 2007, FPGA-based architecture for computing testors. in FPGA-based architecture for computing testors. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4881 LNCS, pp. 188-197, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1/01/14.

FPGA-based architecture for computing testors. / Rojas, Alejandro; Cumplido, René; Carrasco-Ochoa, J. Ariel; Feregrino, Claudia; Martinez-Trinidad, J. Francisco.

FPGA-based architecture for computing testors. 2007. p. 188-197 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4881 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearch

TY - GEN

T1 - FPGA-based architecture for computing testors

AU - Rojas, Alejandro

AU - Cumplido, René

AU - Carrasco-Ochoa, J. Ariel

AU - Feregrino, Claudia

AU - Martinez-Trinidad, J. Francisco

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Irreducible testors (also named typical testors) are a useful tool for feature selection in supervised classification problems with mixed incomplete data. However, the complexity of computing all irreducible testors of a training matrix has an exponential growth with respect to the number of columns in the matrix. For this reason different approaches like heuristic algorithms, parallel and distributed processing, have been developed. In this paper, we present the design and implementation of a custom architecture for BT algorithm, which allows computing testors from a given input matrix. The architectural design is based on a parallel approach that is suitable for high populated input matrixes. The architecture has been designed to deal with parallel processing of all matrix rows, automatic candidate generation, and can be configured for any size of matrix. The architecture is able to evaluate whether a feature subset is a testor of the matrix and to calculate the next candidate to be evaluated, in a single clock cycle. The architecture has been implemented on a Field Programmable Gate Array (FPGA) device. Results show that it provides significant performance improvements over a previously reported hardware implementation. Implementation results are presented and discussed. © Springer-Verlag Berlin Heidelberg 2007.

AB - Irreducible testors (also named typical testors) are a useful tool for feature selection in supervised classification problems with mixed incomplete data. However, the complexity of computing all irreducible testors of a training matrix has an exponential growth with respect to the number of columns in the matrix. For this reason different approaches like heuristic algorithms, parallel and distributed processing, have been developed. In this paper, we present the design and implementation of a custom architecture for BT algorithm, which allows computing testors from a given input matrix. The architectural design is based on a parallel approach that is suitable for high populated input matrixes. The architecture has been designed to deal with parallel processing of all matrix rows, automatic candidate generation, and can be configured for any size of matrix. The architecture is able to evaluate whether a feature subset is a testor of the matrix and to calculate the next candidate to be evaluated, in a single clock cycle. The architecture has been implemented on a Field Programmable Gate Array (FPGA) device. Results show that it provides significant performance improvements over a previously reported hardware implementation. Implementation results are presented and discussed. © Springer-Verlag Berlin Heidelberg 2007.

UR - https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=38449111035&origin=inward

UR - https://www.scopus.com/inward/citedby.uri?partnerID=HzOxMe3b&scp=38449111035&origin=inward

M3 - Conference contribution

SN - 9783540772255

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 188

EP - 197

BT - FPGA-based architecture for computing testors

ER -

Rojas A, Cumplido R, Carrasco-Ochoa JA, Feregrino C, Martinez-Trinidad JF. FPGA-based architecture for computing testors. In FPGA-based architecture for computing testors. 2007. p. 188-197. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).