Aplicação do k-NN utilizando Bitonic Sort

Aplicacao dok-NN

utilizandoBitonic Sort

MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step

Main do CodigoSerial

Ambiente deteste

Resultados

Perguntas?

Aplicacao do k-NN utilizando Bitonic Sort

Maurıcio Jourdan, Paulo Henrique,Pedro Braganick, Vinıcius Coelho

Instituto de InformaticaUniversidade Federal de Goias (UFG)

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Topicos

1 A aplicacao;

2 Codificacao;

3 Resultados;

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Mochila fracionaria

Porque a mochila fracionaria?

Ela utiliza de um algoritmo guloso que visa preencher amochila de forma a maximixar o valor. Utilizando a ordenacao,teremos os valores ja agrupados, onde o n-esimo elementopossui maior valor por unidade de peso.

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Mochila fracionaria

Porque a mochila fracionaria?

Ela utiliza de um algoritmo guloso que visa preencher amochila de forma a maximixar o valor. Utilizando a ordenacao,teremos os valores ja agrupados, onde o n-esimo elementopossui maior valor por unidade de peso.

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Mochila fracionaria

Por exemplo: entre os elementos A, B e C, com respectivosvalores e pesos (1020, 29), (340, 7) e (580, 13), qual a melhorescolha para preencher uma mochila de capacidade 450, deforma que maximize o valor?

Como a mochila aceita valores fracionados, a melhor escolhaseria ordenar estes elementos, de forma que o de maisimportancia sera o elemento com maior valor por unidade depeso.Portanto a ordem ficaria: (1020, 29), (580, 13) e (340, 7).

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Mochila fracionaria

Por exemplo: entre os elementos A, B e C, com respectivosvalores e pesos (1020, 29), (340, 7) e (580, 13), qual a melhorescolha para preencher uma mochila de capacidade 450, deforma que maximize o valor?

Como a mochila aceita valores fracionados, a melhor escolhaseria ordenar estes elementos, de forma que o de maisimportancia sera o elemento com maior valor por unidade depeso.Portanto a ordem ficaria: (1020, 29), (580, 13) e (340, 7).

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Mochila fracionaria

Com a ideia dos k-vizinhos mais proximos, o objetivo e: dadauma mochila de capacidade x, uma posicao n em um vetor eum numero maximo k de elementos adjacentes a n, qual aescolha que maximiza o valor e utiliza a maior capacidadepossıvel da mochila?

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Estrutura

1 #inc l u d e <c s t d i o>2 #inc l u d e <c s t d l i b >3 #inc l u d e <cmath>4 #inc l u d e <u t i l i t y >5 #inc l u d e <i o s t r e a m>6 #de f i n e THREADS 512 // 2ˆ97 #de f i n e BLOCKS 32768 // 2ˆ158 #de f i n e NUM VALS 2∗THREADS∗BLOCKS9 #de f i n e CAPACITY 67108864

10 #de f i n e CUT 10000011 #de f i n e mp m a k e p a i r1213 us ing namespace s t d ;1415 typede f p a i r<i n t , p a i r<double , double> > i d d ;1617 s t r u c t kNN{18 double v a l u e , w e i g h t ;19 kNN( double v a l u e = 0 . 0 , double w e i g h t = 0 . 0 ) : v a l u e ( v a l u e ) ,

w e i g h t ( w e i g h t ) {}20 } ;

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Funcoes

1 vo id p r i n t e l a p s e d ( c l o c k t s t a r t , c l o c k t s t o p ){2 double e l a p s e d = ( ( double ) ( s t o p − s t a r t ) ) / CLOCKS PER SEC ;3 p r i n t f ( ” E l a p s e d t ime : %.3 f s\n” , e l a p s e d ) ;4 }56 /∗Gera c ao a l e a t o r i a dos e l e m e n t o s que compoem o a r r a y ∗/7 double random ( ){8 double r = f a b s ( rand ( ) + rand ( ) ) /CUT;9 i f ( r < 1 . 0 ) r += 1 . 0 ;

10 r e t u r n r ;11 }1213 vo id a r r a y f i l l (kNN ∗a r r , i n t l e n g t h ){14 s r a n d ( t ime (NULL) ) ;15 f o r ( i n t i = 0 ; i < l e n g t h ; ++i ){16 a r r [ i ] . v a l u e = 2∗ c e i l ( random ( ) ) ;17 a r r [ i ] . w e i g h t = c e i l ( random ( ) ) ;18 }19 }

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Fractionary Knapsack

1 i d d f r a c t i o n a r y k n a p s a c k ( kNN ∗v a l u e s , i n t pos , i n t k , doublea t u a l c a p a c i t y ){

2 i n t s t a r t p o s = pos + k − 1 , q t d i t e m s = 0 ;3 double max va lue = 0 . 0 , c a p r e a c h e d = 0 . 0 ;4 i f ( s t a r t p o s >= NUM VALS ) s t a r t p o s = NUM VALS−1;5 f o r ( i n t i = s t a r t p o s ; i >= 0 && i >= pos ; i−− ){6 i f ( v a l u e s [ i ] . w e i g h t == 0 . 0 ) cont inue ;7 i f ( a t u a l c a p a c i t y == 0 . 0 ) break ;8 double aux = a t u a l c a p a c i t y − v a l u e s [ i ] . w e i g h t ; /∗Get t h e amount o f ’ i ’

c a p a b l e to f i l l t h e s a c k∗/9 i f ( aux < 0 . 0 ){

10 double v a l u e u s e d = ( v a l u e s [ i ] . v a l u e / v a l u e s [ i ] . w e i g h t )∗ a t u a l c a p a c i t y ;11 c a p r e a c h e d += a t u a l c a p a c i t y ;12 a t u a l c a p a c i t y = 0 . 0 ;13 max va lue += v a l u e u s e d ;14 v a l u e s [ i ] . w e i g h t −= a t u a l c a p a c i t y ;15 q t d i t e m s ++;16 }17 e l s e{18 a t u a l c a p a c i t y −= v a l u e s [ i ] . w e i g h t ;19 c a p r e a c h e d += v a l u e s [ i ] . w e i g h t ;20 max va lue += v a l u e s [ i ] . v a l u e ;21 v a l u e s [ i ] . w e i g h t = 0 . 0 ;22 q t d i t e m s ++;23 }24 }25 r e t u r n mp( q t d i t e m s , mp( c a p r e a c h e d , max va lue ) ) ;26 }

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Quick Sort

1 vo id swap (kNN ∗a , kNN ∗b ) {2 kNN tmp = ∗a ;3 ∗a = ∗b ;4 ∗b = tmp ;5 }67 i n t p a r t i t i o n (kNN ∗vec , i n t l e f t , i n t r i g h t ){8 i n t i , j ;9 i = l e f t ;

10 f o r ( j = l e f t + 1 ; j <= r i g h t ; ++j ){11 i f ( vec [ j ] . v a l u e / vec [ j ] . w e i g h t > vec [ l e f t ] . v a l u e / vec [ l e f t ] . w e i g h t ) {12 ++i ;13 swap(& vec [ i ] , &vec [ j ] ) ;14 }15 }16 swap(& vec [ l e f t ] , &vec [ i ] ) ;17 r e t u r n i ;18 }1920 vo id q u i c k s o r t (kNN ∗vec , i n t l e f t , i n t r i g h t ) {21 i n t r ;22 i f ( r i g h t > l e f t ){23 r = p a r t i t i o n ( vec , l e f t , r i g h t ) ;24 q u i c k s o r t ( vec , l e f t , r−1) ;25 q u i c k s o r t ( vec , r +1, r i g h t ) ;26 }27 }

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Bitonic Sort

1 vo id b i t o n i c s o r t (kNN ∗ v a l u e s ){2 kNN ∗d e v v a l u e s ;3 s i z e t s i z e = NUM VALS ∗ s i z e o f (kNN) ;45 cudaMal loc ( ( vo id ∗∗) &d e v v a l u e s , s i z e ) ;6 cudaMemcpy ( d e v v a l u e s , v a l u e s , s i z e , cudaMemcpyHostToDevice ) ;78 dim3 b l o c k s (BLOCKS, 1) ; /∗ Number o f b l o c k s ∗/9 dim3 t h r e a d s (THREADS, 1) ; /∗ Number o f t h r e a d s ∗/

1011 /∗ Major s t e p ∗/12 f o r ( i n t k = 2 ; k <= NUM VALS ; k <<= 1 ){13 /∗ Minor s t e p ∗/14 f o r ( i n t j = k>>1; j > 0 ; j = j>>1 ){15 b i t o n i c s o r t s t e p<<<b l o c k s , t h r e a d s>>>( d e v v a l u e s , j , k ) ;16 }17 }18 cudaMemcpy ( v a l u e s , d e v v a l u e s , s i z e , cudaMemcpyDeviceToHost ) ;19 cudaFree ( d e v v a l u e s ) ;20 }

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Bitonic Step

1 g l o b a l vo id b i t o n i c s o r t s t e p (kNN ∗d e v v a l u e s , i n t j , i n t k ){2 uns igned i n t i , i x j ; /∗ S o r t i n g p a r t n e r s : i and i x j ∗/3 i = t h r e a d I d x . x + blockDim . x ∗ b l o c k I d x . x ;4 i x j = i ˆ j ;56 /∗ The t h r e a d s w i t h t h e l o w e s t i d s s o r t t h e a r r a y . ∗/7 i f ( i x j > i ){8 i f ( ( i & k ) == 0 ){9 /∗ S o r t a s c e n d i n g ∗/

10 i f ( d e v v a l u e s [ i ] . v a l u e / d e v v a l u e s [ i ] . w e i g h t <d e v v a l u e s [ i x j ] . v a l u e / d e v v a l u e s [ i x j ] . w e i g h t ){

11 /∗ exchange ( i , i x j ) ; ∗/12 kNN temp = d e v v a l u e s [ i ] ;13 d e v v a l u e s [ i ] = d e v v a l u e s [ i x j ] ;14 d e v v a l u e s [ i x j ] = temp ;15 }16 }17 i f ( ( i & k ) != 0 ){18 /∗ S o r t d e s c e n d i n g ∗/19 i f ( d e v v a l u e s [ i ] . v a l u e / d e v v a l u e s [ i ] . w e i g h t >

d e v v a l u e s [ i x j ] . v a l u e / d e v v a l u e s [ i x j ] . w e i g h t ){20 /∗ exchange ( i , i x j ) ; ∗/21 kNN temp = d e v v a l u e s [ i ] ;22 d e v v a l u e s [ i ] = d e v v a l u e s [ i x j ] ;23 d e v v a l u e s [ i x j ] = temp ;24 }25 }26 }27 }

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Main

1 i n t main ( ){2 c l o c k t s t a r t , s t o p ;3 i n t k , pos ;4 double c a p a c i t y ;5 kNN ∗ v a l u e s = (kNN∗) m a l l o c ( NUM VALS ∗ s i z e o f (kNN) ) ;6 a r r a y f i l l ( v a l u e s , NUM VALS) ;7 pos = rand ( ) % NUM VALS ;8 k = rand ( ) % NUM VALS ;9 c a p a c i t y = rand ( ) % CAPACITY ;

1011 p r i n t f ( ”Number o f v a l u e s : %d\n” , NUM VALS) ;12 p r i n t f ( ” P o s i t i o n : %d\n” , pos ) ;13 p r i n t f ( ”k−n e a r e s t r a n g e : %d\n” , k ) ;14 p r i n t f ( ” C a p a c i t y : %.0 f\n” , c a p a c i t y ) ;1516 s t a r t = c l o c k ( ) ;17 q u i c k s o r t ( v a l u e s , 0 , NUM VALS−1) ; /∗Na v e r s a o p a r a l e l a , t r o c a r a chamada

por b i t o n i c s o r t ( v a l u e s )∗/18 s t o p = c l o c k ( ) ;1920 i d d r e s p = f r a c t i o n a r y k n a p s a c k ( v a l u e s , pos , k , c a p a c i t y ) ;21 p r i n t f ( ”Numbers o f i t e m s i n t h e s a c k : %d\n” , r e s p . f i r s t ) ;22 p r i n t f ( ” C a p a c i t y r e a c h e d : %.0 f\n” , r e s p . second . f i r s t ) ;23 p r i n t f ( ”Maximum v a l u e r e a c h e d : %.2 f\n” , r e s p . second . second ) ;24 p r i n t e l a p s e d ( s t a r t , s t o p ) ;2526 r e t u r n 0 ;27 }

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Ambiente de Teste

GPU: Tesla C2070

CPU: Core 2 Duo 2.4Ghz

448 cores, 1.15Ghz

14 SM (32 cores)

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados

Figure: Quantidade de elementos: 524.288

Speed up: 0.36

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados

Figure: Quantidade de elementos: 524.288

Speed up: 0.36

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados

Figure: Quantidade de elementos: 2.097.152

Speed up: 1.77

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados


Speed up: 1.77

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados


Speed up: 5.91

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados


Speed up: 5.91

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados


Speed up: 11.78

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Resultados


Speed up: 11.78

Aplicacao dok-NN


MaurıcioJourdan,

PauloHenrique,

PedroBraganick,

VinıciusCoelho

Topicos

A aplicacao

Codificacao

Estrutura

Funcoes

FractionaryKnapsack

Quick Sort

Bitonic Sort

Bitonic Step


Ambiente deteste

Resultados

Perguntas?

Perguntas?

Documents

Aplicação do k-NN utilizando Bitonic Sort