Home Documentation Applications NQueens

Solve the N Queens challenge with ProActive !

This example shows how to use ProActive library to distribute and solve the N Queens problem

Description

First of all, it is important to say, that this example is 100% Java and is not optimized. It means that it aims at showing how people can take advantage of ProActive to distribute and solve the N Queens problem. Which algorithm to use, inserting at some points other languages(C, C++, ...) with the Java Native Interface, optimizing java methods are out of scope of this example. Indeed all optimizations are let under users control.

This example involves a NQueenManager controlled by a Graphical Interface, that distributes a set of tasks to Workers. The set of tasks to be performed depends on the queens number.
The first part of this document shows how to run this example, then we detail pieces of code to show how to use ProActive to facilitate distributed Workers deployment thanks to XML Deployment Descriptors, how to redefine the activity of an Active Object to get a specific manner of serving requests and how to take advantage of asynchronous call with futures.

Status

Using the P2P infrsastructure, the ProActive team solved n=25 and hence hold the world record. The number of solutions is 2207893435808352 (2 quadrillion). All details about this world record can be found here. Also available the press release.

Using about 300 machines, n=24, which represents 227514171973736 solutions was solved in 17 days, where it would take about 5 years and 6 month on a single machine.

We have also results about "24 1", "24 2", "24 3":

• "24 1" : 4406487247748 solutions
• "24 2" : 5245516383675 solutions
• "24 3" : 6213832057138 solutions

Download it !!!

Get the full version of the example here

Run it!

Scripts

Screenshot of the interface when running the script

The Manager with 4 registered Workers at the beginning of the application.

Enter the number of queens: 10 for instance, then click on "Task Creation" button.

In the "Number of Tasks" field appears the number of tasks to be performed by workers. In the "Tasks List" panel, a more precise description of those tasks

The Manager after the creation of tasks to distribute.

Click on "Start Computation"

The manager distributes tasks to worker. When all tasks are performed the number of solutions is displayed in the "Nb. solutions" field. The total time for all tasks(hh;mm;ss;ms) is displayed at the end of the "Tasks Lists" panel and on the console as well as the time elapsed (time to solve the problem).

.

The Manager when computation is over.

ProActive code description

You can see the Manager's or worker's source code . We aim in this part at describing ProActive methods calls and features, hence you will see here only the manager's code since most of ProActive calls occur in this class

• main: it is the entry point of the program, this method only instantiates the NQueenManager as an Active object on the local node(no node parameter when calling newActive)
  
  

  String descriptorLocation = args[0];
  try {
   //Creation of the manager as an Active Object on the local node.
   NQueenManager manager = (NQueenManager) ProActive.newActive(NQueenManager.class.getName(),
   new Object[] { descriptorLocation });
   } catch (ActiveObjectCreationException e) {
   e.printStackTrace();
   } catch (NodeException e) {
   e.printStackTrace();
   }

  The newActive call triggers a reflective call to the Manager's constructor that takes a String as parameter

  public NQueenManager(String descriptorUrl) {

  In our case the main method does nothing else than instantiating the NQueenManager since our example is based on a graphical interface to control the manager. We can imagine for an optimized version to call manager's method directly from the main instead of from the GUI.

• Manager's Activity

  public class NQueenManager implements Serializable, RunActive, InitActive

  The manager implements three interfaces: Serializable which is mandatory to be instantiated as an ActiveObject, InitActive, RunActive.
  
  When implementating InitActive an object has to redefine the initActivity method. This method is called only once, just after the constructor. In the example it is where the worker's deployment and the GUI creation occur.

  public void initActivity(Body body) {
   try {
   //get the stub of this active object to create the graphical interface, since it needs a
   //reference on the manager
   NQueenManager manager = (NQueenManager) ProActive.getStubOnThis();
  
   //get the java representation of the xml Deployment Descriptor
   pad = ProActive.getProactiveDescriptor(descriptorUrl);
   
   //activate that descriptor
   pad.activateMappings();
   //get the virtual node nqueenWorker defined in the xml file
   VirtualNode vn = pad.getVirtualNode("nqueenWorker");
  
   //get all the nodes built by activating the descriptor that are mapped to the
   //virtual node nqueenWorker
   Node[] workerNodes = vn.getNodes();

  Here we get the java representation of the XML deployment descriptor passed in parameter to the main method then to the Manager's constructor. With the descriptor used in the example: nqueen.xml, there will be 4 nodes located on the same machine in the workerNodes array. To get more nodes, or to get nodes on different machines just change the descriptor file, or create a new one that you pass as argument to the main method.

  //instantiation of the GUI
   this.managerGUI = new ManagerGUI(manager, pad);
   Object[] param = new Object[1];
   Vector user = new Vector();
  
   // loop to create workers as Active Object. Their constructor requires just one argument:
   // a string that represents their name and which is put in param.
   // We get a stub on each worker that we put in the worker table.
   for (int i = 0; i < workerNodes.length; i++) {
   param[0] = "worker" + i;
   Worker tmp = (Worker) ProActive.newActive(Worker.class.getName(),
   param, workerNodes[i]);
   workerTable.put("worker" + i, tmp);
   user.add("worker" + i);
   }

  Here we loop on the number of nodes to instantiate (as Active Object) as many workers as nodes. It means that to get more workers, you only need to change the descriptor file to create more nodes. For instance if you define 50 nodes in your descriptor, you will get 50 workers. There is no need to change the source code, only the xml file. Since all workers require a String that represents their name (see Worker's constructor) we pass a String as parameter of the newActive call.To instantiate the GUI, we need a reference on the manager, this reference is obtained by calling method ProActive.getStubOnThis()

  managerGUI.setWorkerList(user);
   } catch (Exception ex) {
   ex.printStackTrace();
   }
   }

  When implementating the RunActive interface, an object has to redefine runActivity method. This method defines the way of serving requests. If an object does not implement the RunActive interface a default runActivity method with FIFO behavior is used transparently. In the example the manager is controlled by the graphical interface, so we want to force the order of execution i.e first we wait for a call to createTasks method which is done by clicking on "Task Creation" button, then we wait for a call to startComputation method which is done by clicking on "Start Computation" button. The activity we redifine ensure the order of the execution but on the other hand is not flexible.
  
  It is important to be aware that the design of the application has a major influence on the code. Indeed, if no GUI is used, and all methods are called from the main, FIFO behavior might be enough !!!

  public void runActivity(Body body) {
   // in this method we define a simple activity that can serve only two requests:
   // the creation of task, the distribution of tasks. Calls to other methods of the manager have
   // no effects i.e they will be stored in the request queue but never served. 
   // It is just an example to show how we can redefine the way of serving requests.
   Service service = new Service(body);
  
   while (body.isActive()) {
   //check first if the manager has to create the tasks corresponding to a 
   // queen number
   if (hasToCreateTasks) {
   //Blocks until createTasks is called
   service.blockingServeOldest("createTasks");
   //removes all request in the request queue. Example to show 
   //how to force execution order. Mainly due to the GUI
   service.flushAll();
   hasToCreateTasks = false;
   } else {
   // Blocks until startComputation is called
   service.blockingServeOldest("startComputation");
   //removes all request in the request queue. Example to show 
   //how to force execution order. Mainly due to the GUI
   service.flushAll();
   hasToCreateTasks = true;
   //clear everything
   tasksList.clear();
   futureList.clear();
   resList.clear();
   nbTaskReal = 0;
   }
   }
   }

• Asynchronism and synchronisation method: when startComputation method is called, the manager is responsible to distribute tasks to workers. The method called on the worker is solveTask(Task). The return type of this method is "Task". For the call to be asynchronous the class Task must follow few rules:1) to be Serializable, 2) to be extendable(not final), 3) to provide an empty constructor with no arguments. Since the call is asychronous, the representation of the not yet available result is called a future, hence the call is not-blocking. Once all workers are busy (in the case of course where there are more tasks than workers) we wait until one worker has finished its task. This wait occurs by calling

  ProActive.waitForAny(futureList)

  This methods returns the index of an available result. Then we must remove the result from the futureList.

  Task task = (Task) futureList.remove(j);

  This operation is mandatory since waitForAny method returns the index of the first available future. Then we get the worker that performed the task to give it another task. At the end, when all tasks have been affected, we redistribute tasks for which the result is not yet available in order to ensure that all tasks are going to be performed.
  
  Here is the complete code, we focus on the case where there are more tasks than workers

  //case where there are more tasks than workers
   for (int i = 0; i < workerTable.size(); i++) {
   Task task = (Task) tasksList.get(i);
   checkParity(task);
   task.setAffected(true);
   // Call to method solveTask is asynchronous. Hence the representation of the result
   // which is not yet available is a future, so added in the future list.
   futureList.add(i,
   ((Worker) workerTable.get("worker" + i)).solveTask(task));
   }
   int count = workerTable.size();
   int index = 0;
  
   //while (!futureList.isEmpty()) {
   while (nbTaskReal < tasksList.size()) {
   // All worker are busy, now we wait for the futures to be updated
   // it is done transparently by ProActive. When a result is available we put it
   // in the result table. We identify the worker that performed the task and affect
   // it a new task until all task are done. Calling waitForAny causes the current 
   // Thread to sleep until one result is available. We must then remove the result 
   // from the future list.
   // Same method with a timeout will be provided in the next release.
   int j = ProActive.waitForAny(futureList);
   Task task = (Task) futureList.remove(j);
   task.setDone(true);
   int k = task.getTaskNumber();
  
   //here we identify the worker that performed the task
   String worker = task.getWorker();
  
   //we check if the available result corresponds to a task already performed
   //It may happen when redistributing tasks.
   if (!((Task) resList.get(k)).isDone()) {
   // If the task is not already done
   //remove old task
   resList.remove(k);
   //add completed task 
   resList.add(k, task);
   //increase the counter
   nbTaskReal++;
   // update the GUI
   managerGUI.displayTask(task);
   managerGUI.jTxtNbTasksReal.setText("" + nbTaskReal);
   }
   if (count < tasksList.size()) {
   // there are still tasks to affect
   //get the following task in the Tasks list
   Task followingTask = (Task) tasksList.get(count);
   followingTask.setAffected(true);
   checkParity(followingTask);
   followingTask.setStartDate(new GregorianCalendar());
   futureList.add(((Worker) workerTable.get(worker)).solveTask(
   followingTask));
   count++;
   } else {
   //all tasks have been affected
   //redistributes tasks that did not yet return to avoid deadlock
   Task awaitedTask = searchPendingTask(index);
   index = awaitedTask.getTaskNumber() + 1;
   futureList.add(((Worker) workerTable.get(worker)).solveTask(
   awaitedTask));
   }
   }
   }

• Tips: there are few things to remember when using ProActive, in order to avoid annoying debugs:
  
  
  • Constructor with no-args: this constructor will be used either for the Active Objects creation(if not present, an exception might be thrown) or Future creation for a method call (if not present, the method call is synchronous). Avoid to put initialization stuff in this constructor, as it might lead to unexpected behavior. Indeed this constructor is called for the stub creation.
  
  
  
  • Make your classes implement Serializable interface since ProActive deals with objects that cross the network
  • This tips is more focused on the n queens problem. Indeed it is almost sure that you will deal with primitive types like int, long or final classes like Integer,.... Think to use wrappers instead of primitive types or final classes for methods result type otherwise you will loose the asynchronism capabilities. For instance if one of your worker has a method

     int giveNQueenSolution(parameter)

    calling this method with ProActive is sychronous. So to keep the asynchronism it is advised to use

    MyInteger giveNQueenSolution(parameter)

    In that case call to this method is asynchronous.

    public class MyInteger{
    
    protected int i;
    
     public MyInteger(){
     //empty constructor with no-args
     }
     
     public MyInteger(int i){
     this.i = i;
     }
     
     public int get{
     return i;
     }
     
    }

    Only the methods return type are concerned not the parameters.

  • Contact the ProActive support in case of troubles when using ProActive.

Conclusion

ProActive allows painless deployment of distributed applications and provides also several features that are suitable for the nqueen problem. You can find more documentation like the ProActive Manual or ProActive GuidedTour and also have a look to other examples