Difference between revisions of "The parallelizing Express"

From CDOT Wiki
Jump to: navigation, search
(Created page with "= The parallelizing Express = == Repository == == Team Members == # [mailto:azoeb@myseneca.ca?subject=DPS915 Abbas Zoeb] # [mailto:jjsunga@myseneca.ca?subject=DPS915 Jadria...")
 
(→‎Assignment 1)
Line 10: Line 10:
  
 
== Progress ==
 
== Progress ==
−
=== Assignment 1 ===
+
== Assignment 1 ==
 +
=== SudokuMP ===
 +
 
 +
SudokuMP solves sudoku puzzles given a txt file arranging the puzzle and the size of the puzzle. There are two methods to solve said puzzles the brute force method and the humanistic solver. Profiling wasn't performed on the humanistic solver since it manages to solve all the 16x16 puzzles extremely quickly the worst of them still being under 12ms. The project can be found here: [https://github.com/bendebebe/SudokuMP SudokuMP]
 +
 
 +
The following is a example of the program running with an example input and the output afterwards.
 +
 
 +
==== 16x16 easy 1 ====
 +
 
 +
Before :                                           
 +
00 00 00 00  00 00 00 08  00 00 07 00  00 05 04 00 
 +
00 00 04 00  00 02 16 00  01 05 00 11  09 12 00 00 
 +
00 08 00 07  05 00 15 11  09 04 16 00  02 00 00 00 
 +
05 00 12 16  01 09 00 00  00 13 00 00  00 00 00 06 
 +
 
 +
15 00 10 00  00 00 02 00  00 00 05 00  00 00 16 03 
 +
00 07 00 00  00 00 00 10  06 15 08 00  00 09 02 00 
 +
01 00 13 00  14 00 00 00  10 07 00 09  00 08 00 05 
 +
08 06 00 00  00 00 01 00  14 00 00 03  13 04 00 10 
 +
 
 +
13 00 16 06  15 00 00 09  00 11 00 00  00 00 01 02 
 +
03 00 08 00  12 00 06 01  00 00 00 07  00 16 00 13 
 +
00 05 01 00  00 14 08 07  16 00 00 00  00 00 12 00 
 +
07 04 00 00  00 11 00 00  00 09 00 00  00 14 00 08 
 +
 
 +
16 00 00 00  00 00 12 00  00 00 06 01  15 02 00 09 
 +
00 00 00 01  00 08 10 06  12 16 00 13  04 00 03 00 
 +
00 00 11 08  02 00 09 15  00 03 04 00  00 13 00 00 
 +
00 03 06 00  00 16 00 00  05 00 00 00  00 00 00 00 
 +
 
 +
After :
 +
 
 +
11 01 09 10  06 13 03 08  02 14 07 12  16 05 04 15 
 +
06 15 04 13  10 02 16 14  01 05 03 11  09 12 08 07 
 +
14 08 03 07  05 12 15 11  09 04 16 06  02 10 13 01 
 +
05 02 12 16  01 09 07 04  08 13 10 15  03 11 14 06 
 +
 
 +
15 11 10 09  08 07 02 12  13 01 05 04  14 06 16 03 
 +
12 07 14 03  13 05 04 10  06 15 08 16  01 09 02 11 
 +
01 16 13 04  14 06 11 03  10 07 02 09  12 08 15 05 
 +
08 06 02 05  09 15 01 16  14 12 11 03  13 04 07 10 
 +
 
 +
13 14 16 06  15 10 05 09  04 11 12 08  07 03 01 02 
 +
03 10 08 11  12 04 06 01  15 02 14 07  05 16 09 13 
 +
09 05 01 02  03 14 08 07  16 06 13 10  11 15 12 04 
 +
07 04 15 12  16 11 13 02  03 09 01 05  10 14 06 08 
 +
 
 +
16 13 07 14  04 03 12 05  11 08 06 01  15 02 10 09 
 +
02 09 05 01  11 08 10 06  12 16 15 13  04 07 03 14 
 +
10 12 11 08  02 01 09 15  07 03 04 14  06 13 05 16 
 +
04 03 06 15  07 16 14 13  05 10 09 02  08 01 11 12 
 +
 
 +
NOTE : The profiles for this project were quite large so only the most used functions are listed here. The entire profile file can be find through the links provided above the respective flat profile.
 +
 
 +
Link to full profile : [http://pastebin.com/ah48EGab FULL]
 +
 
 +
Flat Profile :
 +
  %  cumulative  self              self    total         
 +
time  seconds  seconds    calls  s/call  s/call  name   
 +
65.87      0.81    0.81    59789    0.00    0.00  create_copy_board(Board*)
 +
21.14      1.07    0.26    59777    0.00    0.00  choose_cell_bf(Board*, int&, int&)
 +
  6.51      1.15    0.08    59790    0.00    0.00  Board::Board(int)
 +
  6.51      1.23    0.08    59777    0.00    0.00  Board::~Board()
 +
  0.00      1.23    0.00  179709    0.00    0.00  clear_number(Board*, int, Align, int)
 +
  0.00      1.23    0.00  179370    0.00    0.00  Board* const& std::forward<Board* const&>(std::remove_reference<Board* const&>::type&)
 +
  0.00      1.23    0.00    59903    0.00    0.00  update_solution(Board*, int, int, int)
 +
  0.00      1.23    0.00    59790    0.00    0.00  _ZN9__gnu_cxx13new_allocatorIP5BoardE9constructIS2_IRKS2_EEEvPT_DpOT0_
 +
  0.00      1.23    0.00    59790    0.00    0.00  std::enable_if<std::__and_<std::allocator_traits<std::allocator<Board*> >::__construct_helper<Board*, Board* const&>::type>::value, void>::type std::allocator_traits<std::allocator<Board*> >::_S_construct<Board*, Board* const&>(std::allocator<Board*>&, Board**, Board* const&)
 +
  0.00      1.23    0.00    59790    0.00    0.00  decltype (_S_construct({parm#1}, {parm#2}, (forward<Board* const&>)({parm#3}))) std::allocator_traits<std::allocator<Board*> >::construct<Board*, Board* const&>(std::allocator<Board*>&, Board**, Board* const&)
 +
  0.00      1.23    0.00    59790    0.00    0.00  std::deque<Board*, std::allocator<Board*> >::push_back(Board* const&)
 +
  0.00      1.23    0.00    59790    0.00    0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::push(Board* const&)
 +
  0.00      1.23    0.00    59790    0.00    0.00  operator new(unsigned long, void*)
 +
  0.00      1.23    0.00    59784    0.00    0.00  std::_Deque_iterator<Board*, Board*&, Board**>::_Deque_iterator(std::_Deque_iterator<Board*, Board*&, Board**> const&)
 +
  0.00      1.23    0.00    59780    0.00    0.00  std::deque<Board*, std::allocator<Board*> >::end()
 +
  0.00      1.23    0.00    59778    0.00    0.00  void __gnu_cxx::new_allocator<Board*>::destroy<Board*>(Board**)
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::_Deque_iterator<Board*, Board*&, Board**>::operator*() const
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::deque<Board*, std::allocator<Board*> >::empty() const
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::empty() const
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::_Deque_iterator<Board*, Board*&, Board**>::operator--()
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::enable_if<std::__and_<std::allocator_traits<std::allocator<Board*> >::__destroy_helper<Board*>::type>::value, void>::type std::allocator_traits<std::allocator<Board*> >::_S_destroy<Board*>(std::allocator<Board*>&, Board**)
 +
  0.00      1.23    0.00    59778    0.00    0.00  void std::allocator_traits<std::allocator<Board*> >::destroy<Board*>(std::allocator<Board*>&, Board**)
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::deque<Board*, std::allocator<Board*> >::back()
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::deque<Board*, std::allocator<Board*> >::pop_back()
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::pop()
 +
  0.00      1.23    0.00    59778    0.00    0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::top()
 +
  0.00      1.23    0.00    59778    0.00    0.00  bool std::operator==<Board*, Board*&, Board**>(std::_Deque_iterator<Board*, Board*&, Board**> const&, std::_Deque_iterator<Board*, Board*&, Board**> const&)
 +
  0.00      1.23    0.00    59777    0.00    0.00  update_stack(Board*)
 +
  0.00      1.23    0.00      24    0.00    0.00  std::__deque_buf_size(unsigned long)

Revision as of 23:13, 7 February 2017

The parallelizing Express

Repository

Team Members

  1. Abbas Zoeb
  2. Jadrian Sunga
  3. Marko Radmanovic
Email All

Progress

Assignment 1

SudokuMP

SudokuMP solves sudoku puzzles given a txt file arranging the puzzle and the size of the puzzle. There are two methods to solve said puzzles the brute force method and the humanistic solver. Profiling wasn't performed on the humanistic solver since it manages to solve all the 16x16 puzzles extremely quickly the worst of them still being under 12ms. The project can be found here: SudokuMP

The following is a example of the program running with an example input and the output afterwards.

16x16 easy 1

Before : 00 00 00 00 00 00 00 08 00 00 07 00 00 05 04 00 00 00 04 00 00 02 16 00 01 05 00 11 09 12 00 00 00 08 00 07 05 00 15 11 09 04 16 00 02 00 00 00 05 00 12 16 01 09 00 00 00 13 00 00 00 00 00 06

15 00 10 00 00 00 02 00 00 00 05 00 00 00 16 03 00 07 00 00 00 00 00 10 06 15 08 00 00 09 02 00 01 00 13 00 14 00 00 00 10 07 00 09 00 08 00 05 08 06 00 00 00 00 01 00 14 00 00 03 13 04 00 10

13 00 16 06 15 00 00 09 00 11 00 00 00 00 01 02 03 00 08 00 12 00 06 01 00 00 00 07 00 16 00 13 00 05 01 00 00 14 08 07 16 00 00 00 00 00 12 00 07 04 00 00 00 11 00 00 00 09 00 00 00 14 00 08

16 00 00 00 00 00 12 00 00 00 06 01 15 02 00 09 00 00 00 01 00 08 10 06 12 16 00 13 04 00 03 00 00 00 11 08 02 00 09 15 00 03 04 00 00 13 00 00 00 03 06 00 00 16 00 00 05 00 00 00 00 00 00 00

After :

11 01 09 10 06 13 03 08 02 14 07 12 16 05 04 15 06 15 04 13 10 02 16 14 01 05 03 11 09 12 08 07 14 08 03 07 05 12 15 11 09 04 16 06 02 10 13 01 05 02 12 16 01 09 07 04 08 13 10 15 03 11 14 06

15 11 10 09 08 07 02 12 13 01 05 04 14 06 16 03 12 07 14 03 13 05 04 10 06 15 08 16 01 09 02 11 01 16 13 04 14 06 11 03 10 07 02 09 12 08 15 05 08 06 02 05 09 15 01 16 14 12 11 03 13 04 07 10

13 14 16 06 15 10 05 09 04 11 12 08 07 03 01 02 03 10 08 11 12 04 06 01 15 02 14 07 05 16 09 13 09 05 01 02 03 14 08 07 16 06 13 10 11 15 12 04 07 04 15 12 16 11 13 02 03 09 01 05 10 14 06 08

16 13 07 14 04 03 12 05 11 08 06 01 15 02 10 09 02 09 05 01 11 08 10 06 12 16 15 13 04 07 03 14 10 12 11 08 02 01 09 15 07 03 04 14 06 13 05 16 04 03 06 15 07 16 14 13 05 10 09 02 08 01 11 12

NOTE : The profiles for this project were quite large so only the most used functions are listed here. The entire profile file can be find through the links provided above the respective flat profile.

Link to full profile : FULL

Flat Profile : 

 %   cumulative   self              self     total           
time   seconds   seconds    calls   s/call   s/call  name    
65.87      0.81     0.81    59789     0.00     0.00  create_copy_board(Board*)
21.14      1.07     0.26    59777     0.00     0.00  choose_cell_bf(Board*, int&, int&)
 6.51      1.15     0.08    59790     0.00     0.00  Board::Board(int)
 6.51      1.23     0.08    59777     0.00     0.00  Board::~Board()
 0.00      1.23     0.00   179709     0.00     0.00  clear_number(Board*, int, Align, int)
 0.00      1.23     0.00   179370     0.00     0.00  Board* const& std::forward<Board* const&>(std::remove_reference<Board* const&>::type&)
 0.00      1.23     0.00    59903     0.00     0.00  update_solution(Board*, int, int, int)
 0.00      1.23     0.00    59790     0.00     0.00  _ZN9__gnu_cxx13new_allocatorIP5BoardE9constructIS2_IRKS2_EEEvPT_DpOT0_
 0.00      1.23     0.00    59790     0.00     0.00  std::enable_if<std::__and_<std::allocator_traits<std::allocator<Board*> >::__construct_helper<Board*, Board* const&>::type>::value, void>::type std::allocator_traits<std::allocator<Board*> >::_S_construct<Board*, Board* const&>(std::allocator<Board*>&, Board**, Board* const&)
 0.00      1.23     0.00    59790     0.00     0.00  decltype (_S_construct({parm#1}, {parm#2}, (forward<Board* const&>)({parm#3}))) std::allocator_traits<std::allocator<Board*> >::construct<Board*, Board* const&>(std::allocator<Board*>&, Board**, Board* const&)
 0.00      1.23     0.00    59790     0.00     0.00  std::deque<Board*, std::allocator<Board*> >::push_back(Board* const&)
 0.00      1.23     0.00    59790     0.00     0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::push(Board* const&)
 0.00      1.23     0.00    59790     0.00     0.00  operator new(unsigned long, void*)
 0.00      1.23     0.00    59784     0.00     0.00  std::_Deque_iterator<Board*, Board*&, Board**>::_Deque_iterator(std::_Deque_iterator<Board*, Board*&, Board**> const&)
 0.00      1.23     0.00    59780     0.00     0.00  std::deque<Board*, std::allocator<Board*> >::end()
 0.00      1.23     0.00    59778     0.00     0.00  void __gnu_cxx::new_allocator<Board*>::destroy<Board*>(Board**)
 0.00      1.23     0.00    59778     0.00     0.00  std::_Deque_iterator<Board*, Board*&, Board**>::operator*() const
 0.00      1.23     0.00    59778     0.00     0.00  std::deque<Board*, std::allocator<Board*> >::empty() const
 0.00      1.23     0.00    59778     0.00     0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::empty() const
 0.00      1.23     0.00    59778     0.00     0.00  std::_Deque_iterator<Board*, Board*&, Board**>::operator--()
 0.00      1.23     0.00    59778     0.00     0.00  std::enable_if<std::__and_<std::allocator_traits<std::allocator<Board*> >::__destroy_helper<Board*>::type>::value, void>::type std::allocator_traits<std::allocator<Board*> >::_S_destroy<Board*>(std::allocator<Board*>&, Board**)
 0.00      1.23     0.00    59778     0.00     0.00  void std::allocator_traits<std::allocator<Board*> >::destroy<Board*>(std::allocator<Board*>&, Board**)
 0.00      1.23     0.00    59778     0.00     0.00  std::deque<Board*, std::allocator<Board*> >::back()
 0.00      1.23     0.00    59778     0.00     0.00  std::deque<Board*, std::allocator<Board*> >::pop_back()
 0.00      1.23     0.00    59778     0.00     0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::pop()
 0.00      1.23     0.00    59778     0.00     0.00  std::stack<Board*, std::deque<Board*, std::allocator<Board*> > >::top()
 0.00      1.23     0.00    59778     0.00     0.00  bool std::operator==<Board*, Board*&, Board**>(std::_Deque_iterator<Board*, Board*&, Board**> const&, std::_Deque_iterator<Board*, Board*&, Board**> const&)
 0.00      1.23     0.00    59777     0.00     0.00  update_stack(Board*)
 0.00      1.23     0.00       24     0.00     0.00  std::__deque_buf_size(unsigned long)
Retrieved from "https://wiki.cdot.senecapolytechnic.ca/w/index.php?title=The_parallelizing_Express&oldid=123288"