Hello, I’m new to CUDA and JCUDA and maybe my question could be out of place, I’m sorry if that is the case.
I’m trying to optimize a process using GPUs, the process is to calculate all possible combinations of players to form partitions. To understand my problem, I use the following example. For exampe we have a set of players N = {1,2,3,4,5}, this players are regrouped like this {1,2},{3,4},{5}. It means palyer 1 will play with player 2 as a single player, and so one. Each group of players has a set of strategies or choices. Each player chooses the group to which he wants to belong, for example:
the group {1,2} has these possibilites {{1,2};{1,2,3,4}}; i.e the players {1,2} either they choose to stay together or to join the group{3,4}.
the same explanation for the rest of players:{3,4}=>{{3,4};{3,4,5};{1,2,3,4}}
{5}=>{{5};{3,4,5}}.
Now, the group of players choosing the same strategy will be form a new group (coalition). For example, group{1,2} chose the strategy {1,2,3,4} ;ie. the players {1,2} want to form a new group with players{3,4}. Players {3,4} choose {3,4,5}, player{5} choose {3,4,5}. The players have chosen the same strategy will group together to form in the final a partition of plyaers like this: so the partition of players formed here is :{1,2},{3,4,5}. W e do the same with all possible combinations of players’ strategies to obtain all possible partitions of players.
Now my question is if it is possible to use parallilism with JCUDA to compute all possible partitions of players, especially when we have many players, for example |N|=1000 , then we have 1000^1000 possible partitions!!!
I have programed this process as a recursive function to get all possible partitions of players like this:
import java.util.ArrayList;
import java.util.Hashtable;
public class Partitions {
public Hashtable<ArrayList<Integer>, ArrayList<ArrayList<Integer>>> HashTab = new Hashtable<ArrayList<Integer>,ArrayList<ArrayList<Integer>>>(); // The key is the chosen strategy(coalition) and the value is the group of players have chosen the same coalition(strategy).
// create partitions combination
public void CalculStrategiesCombination ( int index, ArrayList<ObjectsCoalitions> PlayerCoalitions, int K,int L) {
index = index +1;
if(index < PlayerCoalitions.size()){
for(int j =0; j< PlayerCoalitions.get(index).Coaltions.size(); j++){
if(!this.HashTab.containsKey(PlayerCoalitions.get(index).Coaltions.get(j))){
ArrayList<ArrayList<Integer>> e = new ArrayList<ArrayList<Integer>>();
e.add(PlayerCoalitions.get(index).Objects);
this.HashTab.put(PlayerCoalitions.get(index).Coaltions.get(j), e);
}
else{
this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).add(PlayerCoalitions.get(index).Objects);
}
if(this.HashTab.size()<K){
CalculStrategiesCombination (index, PlayerCoalitions,K,L);
}
if(this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).size()==1){
this.HashTab.remove(PlayerCoalitions.get(index).Coaltions.get(j));
}
else{
this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).remove(this.HashTab.get(PlayerCoalitions.get(index).Coaltions.get(j)).size()-1);
}
}
}
else {
// Treatement.......
}
}
}
public class ObjectsCoalitions {
public ArrayList<Integer>Objects = new ArrayList<Integer>(); // for example Objects = {1,2}
public ArrayList<ArrayList<Integer>> Coaltions = new ArrayList<ArrayList<Integer>> (); // coalitions (strategis)={{1,2};{1,2,3,4}}
}
Please I want to know if it is possible to resolve this problem with jcuda, and what I must do and by what I must start, as i said I’m new with jcuda and cuda. Any suggestions please ?!
Thanks in advance. Best regards.
- this is completely out of scope of any computation)