NPRG054 - High Performance Software Development

David Bednárek

Official webpage

Slides

(under eternal construction/translation)

Timeline of seminars and assignments

SeminarAssignment #6 bitcountAssignment #5Assignment #3
23.2.2017assignment
(9.3.2017 cancelled)
23.3.2017deadlineassignment
6.4.2017assignment
20.4.2017evaluationdeadline
4.5.2017evaluationdeadline
18.5.2017evaluation

Homework assignments


Assignment 6 - Bit counting

Create a class named bitarray<P> which represents an array of bits and supports the following operations:

Array size is specified as an argument to constructor; allocation is done during construction. The set/reset operations shall have constant complexity, the others shall be linear wrt. array size. The counting operation is expected to be slower than the others (i.e. the count shall not be precomputed during other operations).

The template argument P is used to specify the vector platform available. You shall define the following three policy classes: policy_sse, policy_avx, and policy_avx512. You shall implement bitarray<policy_sse>, bitarray<policy_avx>, and bitarray<policy_avx512>.

The test wrapper du6main.cpp uses policy_sse by default, other policies may be selected using command-line argument "avx" or "avx512".

If you use AVX512 instruction, be aware that not every compiler supports them. Hide the parts which use AVX512 into "#ifdef USE_AVX512" directives to avoid error messages in non-supporting compilers and define the macro if your compiler supports it. du6main.cpp will not require policy_avx512 if this macro is not defined.

If you do not want to implement specific AVX512 implementation, define policy_avx512 equal to policy_avx.

The du6bitcount.hpp (as distributed) contains implementation based on int64_t blocks and 8-bit lookup for bitcounting (all policy classes are identical).

The empty.err file contains stderr output of the test wrapper. Your implementation shall produce the same contents.

The test wrapper outputs measured time (in nanoseconds per bit). Note that the count operation is measured together with an and operation (to detect tricks like precomputing the count). The reference implementation shows the following times (for 1M of bits):


DÚ 5 - "Násobení" matic

Referenční algoritmus

uint16_t a[L][N], b[N][M], c[L][M];
	
for( i = 0; i < L; ++ i)
  for( j = 0; j < M; ++ j)
  {
    c[i][j] = 0xFFFF;
    for( k = 0; k < N; ++ k)
      c[i][j] = std::min( c[i][j], a[i][k] + b[k][j]);
  }

Matice

Datová struktura pro matici a operace násobení.

Předepsané rozhraní matice

Umožňuje připojení k testovacímu mechanismu.

class matrix {
public:
	matrix(size_t m, size_t n);
	size_t vsize() const;
	size_t hsize() const;
	bool get(size_t i, size_t j) const;
	void set(size_t i, size_t j, bool e);
	void assign_mul(const matrix & a, const matrix & b);
private: // ...
};

DÚ 3 - Binární vyhledávání

Vstupem je setříděná posloupnost idata o velikosti isize a nesetříděná posloupnost odata o velikosti osize. Úkolem je roztřídit odata do (isize+1) skupin, jejichž hraniční hodnoty jsou dány posloupností idata. V k-té skupině jsou prvky větší nebo rovné idata[k-1] a menší než idata[k].

	typedef std::int32_t data_element;
	
	template< typename policy>
	class bsearch_inner {
	public:
		bsearch_inner( const data_element * idata, std::size_t isize);
	};
	template< typename policy>
	class bsearch_outer { 
	public:
		bsearch_outer( const bsearch_inner< policy> & inner, std::size_t osize);

		void bucketize( const data_element * odata);
		
		typedef std::pair< const data_element *, std::size_t> bucket_rv;

		bucket_rv bucket( std::size_t k) const;
	};

DÚ 1 - Polymorfní datová struktura


DÚ 4 - Levenstein

Jednovláknová verze úlohy z NPRG042 Programování v paralelním prostředí.

class levenstein {
public:
	typedef int data_element;

	template< typename I1, typename I2>
	levenstein(I1 i1b, I1 i1e, I2 i2b, I2 i2e);

	data_element compute();
};

Levensteinova distance řetězců A[0..M-1], B[0..N-1] je definována předpisem:

	D(0,0) = 0;
	D(0,j) = j;
	D(i,0) = i;
	D(i+1,j+1) = min( D(i,j+1) + 1, D(i,j) + (A[i]==B[j] ? 0 : 1), D(i+1,j) + 1);
	D = D(M,N);

Elementy porovnávaných řetězců jsou 32-bitová čísla, do stejného typu data_element se vejde i výsledná vzdálenost.

Konstruktor třídy akceptuje dvě dvojice iterátorů, každá z nich určuje jeden z porovnávaných řetězců. Úkolem konstruktoru je okopírovat data do vnitřních struktur. Čas konstruktoru se neměří, předpokládá se lineární vzhledem k délce řetězců.

Funkce compute spočítá Levensteinovu vzdálenost a vrátí ji. Testovací obálka vypisuje její čas dělený součinem velikostí řetězců, tedy čas na jeden element matice. Vzorové řešení zvládá porovnání dvou 32K řetězců za méně než sekundu.