Divide and conquer faster and efficiently than ever before

machine1

RDB project

Divide and conquer faster and efficiently than ever before

RDB project

Project – Description

Our project deals with solving decomposable problems “divide and conquer” problems. Our system breaks the “Big Problem” into small subproblems, according to the definition and solves them using maximum computing resources (all the cores in the CPU). Until a solution to the Big (original) Problem is reached, the system assigns each subproblem to an available hardware resource. The resource solves the subproblem it received and returns the solution back to the system. The system receives the solution, and checks if there are more subproblems to solve. If there still are unresolved subproblems, it assigns them to available resources, until the Big Problem is resolved. Until the Big Problem is resolved, all cores are busy.

The problem

The inability to solve big problems of “divide and conquer” effectively, using maximum resources.

The solution

There is two main problems that our platform provides a solution for them:

  1. Finding solutions for “divide and conquer” problems by maximizing resource utilization: the system does it by breaking the “Big Problem” into smaller subproblems and continuously sending each of them to an available core for solution. All cores work in parallel, providing solutions to the subproblems sand sending them back to the system. The system receives the solutions of the subproblems and merges them into a solution for the Big Problem.
  2. The platform provides a convenient workspace for the programmer to adjust it to a large decomposable problem.

How does the system work?

  1. Hardware check- checks all the connected hardware and identifies the existing CPUs and their cores.
  2. Problem break – the system breaks the “Big Problem” into small subproblems, according to a pre-defined subproblem size.
  3. Subproblem assignment – the system sends each unresolved subproblem to an available core for solution core.
  4. Work – each core receives a subproblem and starts solving it. When the core finds the solution for the subproblem, it sends the solution to the system.
  5. Merge solutions – each time the system receives a new solution it merges it with the solutions it has already received from the various cores.
  6. Assign a new unresolved subproblem – each time the system receives a new solution from one of the cores, it checks if there is still an unresolved subproblem. If there is, it sends it to an available core.
  7. End – when there are no more unresolved subproblems, the system closes all the treads of all cores. Then it outputs the solution of the “Big Problem” which is the result of the merging of the solutions that occured in stage 5.

Submitted by: Guy bonne & Max Gontarenko

Accessibility
Close Close