Algo

Repartition decpu load "decoupe de rectangle", et C++

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : Repartition decpu load "decoupe de rectangle", et C++

xiluoc

un pc pour les unirs ....

:hello: ,
j explique :
On donne un nombre P de processeurs
il y a NxM taches a partager.
Le bute est de minimiser le total des tache que n importe quel pc recevra.
Les contraintes sont :
- Chaque tache ne peus pas etre partage entre les pc.
- Toutes taches alouer a un pc doivent etre un sous rectangle de la matrix

Dans l example 1
le max load est 12 ( 1 + 2 +3 + 1 + 2 +3 ) mais on vois bien que si on avait couper differement
1 2 et 3
1 2 3
1 2 3

on aurait eu 9 taches pour les 2 pc c etait parfait.

Ma question est vers quel algo regarder, je devrais peut etre choisir entre efficacite et reponses optimales.
Comment aborder le problem ? est ce un problem connu en algo ?

merci :jap:

Message édité par xiluoc le 10-08-2005 à 00:24:08

Publicité

xiluoc

un pc pour les unirs ....

xiluoc

un pc pour les unirs ....

apperement cest un problem np, la solution parfaite prendrais un peu trop de temps. jai trouve pas mal d algo de partitionement pour les graphs mais la cest une matrice simple.

xiluoc

un pc pour les unirs ....

xiluoc

un pc pour les unirs ....

a vot bon coeur

phosphorus68

Pseudo à n°

J'aurais fait des rectangles de 1x1 [:dawa]
Ensuite le problème se ramène à sommer toutes les valeurs de la matrice, diviser par le nombre de procs et à tomber le plus près possible juste un peu au-delà de (total/p)

Si j'ai bien lu ton énoncé, y aucune contrainte pour répondre comme cela [:joce] (ou ta phrase "toutes taches ..." ne respecte aucune règle syntaxique en vigueur dans notre beau pays )

dividee

Je connais pas grand chose à ce genre de problème, mais pourquoi pas appliquer "diviser pour régner" ? C'est peut-être simpliste, mais ça donne quand-même la solution optimale pour tous les exemples que tu as donné. Je l'ai testé sur des plus grosses matrices générées aléatoirement, et les résultats semblent pas trop mauvais...

En détail:
Si il y a qu'un seul processeur, c'est trivial

S'il y a deux processeurs, c'est facile: pour un matrice N x M, il n'y a que (N-1)+(M-1) partitionnements possibles, on peut les essayer tous. La meilleur répartition sera celle dont le rapport des charges sera la plus proche de 1.

S'il y a plus de 2 processeurs, on subdivise en deux comme pour le cas précédent, puis on résout chaque sous-problème avec la moitié des processeurs...

Une amélioration: si le nombre de processeur est impair (2n+1), un des sous-problème aura n processeurs et l'autre n+1; on peut donc viser un rapport de (n+1)/n pour le partitionnement au lieu de 1...

[edit]
petite correction, ça ne donne pas la solution optimale pour l'exemple 4, ça me donne 122, alors qu'il y a moyen de faire 120.

Message édité par dividee le 08-08-2005 à 05:13:07

xiluoc

un pc pour les unirs ....

jai implementer le brute force pour 2 cpu, ca marche maintenant faut que jessaye le deivide and conqueer.
je trouve moncode un peu lourd quand meme, quelques critique ?

Code :

//case 2 cpu
int partA = 0;
int partB = 0;
double bestRatioSofar = 0;
double Ratio = 0;
int sum = 0;
int curentCut = 1;
int maxLoad = 0;
int bestCutPosition = 0;
//row = true col = false;
bool colOrRowCut = true;
// do rows
// m-1 possibilities of arrangement
for (int i =0; i < rowSize -1 ; i++)
{
for (int k = 0; k < curentCut; k++)
{
//cout << "part A include row " << k << endl;
for (int j = 0; j < colSize; j ++)
{
sum += matrix[k][j];
}
partA = sum;
}
sum = 0;
for (int k = curentCut ; k < rowSize ; k++)
{
//cout << "part B include row " << k << endl;
for (int j = 0; j < colSize; j ++)
{
sum += matrix[k][j];
}
partB = sum;
}
if (partA > partB) Ratio = (double)partA / (double)partB;
else Ratio = (double)partB / (double)partA;
//update best ratiosofar
if (Ratio < bestRatioSofar || bestRatioSofar == 0)
{
bestRatioSofar = Ratio;
colOrRowCut = true;
bestCutPosition = curentCut;
if (partA > partB) maxLoad = partA;
else maxLoad = partB;
}
//cout << " part A : " << partA << " part B : " << partB << " ratio " << Ratio << endl;
partA = 0;
partB = 0;
sum = 0;
curentCut++;
}
curentCut = 1;
// do cols
//n-1 possibilities of arrangement
for (int i =0; i < colSize -1 ; i++)
{
for (int k = 0; k < curentCut; k++)
{
// cout << "part A include col " << k << endl;
for (int j = 0; j < rowSize; j ++)
{
sum += matrix[j][k];
}
partA = sum;
}
sum = 0;
for (int k = curentCut ; k < rowSize ; k++)
{
// cout << "part B include col " << k << endl;
for (int j = 0; j < rowSize; j ++)
{
sum += matrix[j][k];
}
partB = sum;
}
if (partA > partB) Ratio = (double)partA / (double)partB;
else Ratio = (double)partB / (double)partA;
//update best ratiosofar
if (Ratio < bestRatioSofar || bestRatioSofar == 0)
{
bestRatioSofar = Ratio;
colOrRowCut = false;
bestCutPosition = curentCut;
if (partA > partB) maxLoad = partA;
else maxLoad = partB;
}
//cout << " part A : " << partA << " part B : " << partB << " ratio " << Ratio << endl;
partA = 0;
partB = 0;
sum = 0;
curentCut++;
}
cout << "The maximum load (first line) followed by/nthe " <<procNbr << " regions selected are (top row, left column, bottom row, right column):" << endl;
cout << maxLoad << endl;

:jap:

xiluoc

un pc pour les unirs ....

je pense avoir reussi a implementer divide and conquer pour un nombre pair de cpu , a lexemple 4 ma de coupe se fait de :

top row, left col, down row, right col
0 0 4 0
0 1 4 1
0 2 3 4
4 2 4 4

ton Algo trouve la meme chose ?
max load de 122
ca mas pris 200 lignes de code

dividee

La solution précise trouvée dépend sûrement de petits détails d'implémentation, mais la qualité de cette solution devrait rester la même en moyenne...

Pour l'exemple 4 j'obtiens ceci (j'ai numéroté les lignes/colonnes en partant de 1):
1 1 2 5 load: 10
3 1 4 5 load: 10
5 1 5 2 load: 2
5 3 5 5 load: 122

J'ai implémenté l'algo en python; le C j'en fais plus que si je suis obligé

Code :

def solve(mat, n):
rects = []
def _solve(n, rect):
if n == 1:
rects.append(rect)
else:
if rect[2] == rect[0] and rect[3] == rect[1]:
# more than 1 processor for a single task ?
for i in xrange(n-1):
rects.append((0,0,0,0)) # all processors are idle
rects.append(rect) # except one
else:
half_n = n/2
ratio = float(n - half_n) / half_n
r1, r2 = partition(rect, ratio)
_solve(n-half_n, r1)
_solve(half_n, r2)
def partition(rect, ratio):
best_diff = 1e100 # some big float
top, left, bottom, right = rect
whole_rect_sum = sum_rect(rect)
# split by lines
sum1 = 0
for split in xrange(top, bottom):
r1 = (top, left, split, right)
r2 = (split+1, left, bottom, right)
sum1 += sum_rect((split,left,split,right))
sum2 = whole_rect_sum - sum1
if sum1 < sum2:
r1, r2 = r2, r1
r = float(sum2)/sum1
else:
r = float(sum1)/sum2
if abs(r-ratio) < best_diff:
best_diff = abs(r-ratio)
best_r1 = r1
best_r2 = r2
# split by columns
sum1 = 0
for split in xrange(left, right):
r1 = (top, left, bottom, split)
r2 = (top, split+1, bottom, right)
sum1 += sum_rect((top,split,bottom,split))
sum2 = whole_rect_sum - sum1
if sum1 < sum2:
r1, r2 = r2, r1
r = float(sum2)/sum1
else:
r = float(sum1)/sum2
if abs(r-ratio) < best_diff:
best_diff = abs(r-ratio)
best_r1 = r1
best_r2 = r2
return (best_r1, best_r2)
def sum_rect(r):
top, left, bottom, right = r
return sum(sum(line[left-1:right]) for line in mat[top-1:bottom])
_solve(n, (1,1, len(mat), len(mat[0])))
loads = [sum_rect(r) for r in rects]
response = zip(loads, rects)
response.sort(reverse=True) # highest load first
return response

66 lignes, moins si je n'avais pas fait qqes optimisations. J'ai malheureusement écrasé la version non optimisée, mais les optimisations ont surtout pour but d'appeler moins souvent sum_rect; tu peux remplacer les calculs de sum1 et sum2 dans les boucles for de la fonction partition par sum1=sum_rect(r1) et sum2=sum_rect(r2) pour comprendre comment ça marche sans te laisser distraire par les optimisations. Je suis pas certain à 100% que c'est "bug free", mais j'ai quand-même prévu le cas où il essayerait de partager une tâche entre plusieurs processeurs.

Moins de 20 secondes pour une matrice de 1000x1000 et 10000 processeurs, mais qui a autant de processeurs à disposition ?

Je n'ai pas lu ton code C (pardon, C++, mais ça ressemble à du C ), mais à priori tu aurais intérêt à modulariser un peu en découpant l'algo en plusieurs fonctions...

Les tests:

Code :

mat1 = ((1,2,3),)*3
mat2 = (((1,)*4),)*4
mat3 = (((1,)*4),)*3 + ((1,120,1,1),)
mat4 = (((1,)*5),)*4 + ((1,1,120,1,1),)
mat5 = ((1,120,1), (1,1,1), (1,1,1))
tests = [ # (matrix, num_processors)
(mat1, 2),
(mat2, 2),
(mat3, 3),
(mat4, 4),
(mat5, 2),
]
print
for idx, test in enumerate(tests):
print "Example", idx+1
print solve(*test)
print "\nA more complex example"
from random import seed,randint
seed(0)
mat_size = 20
nproc = 20
mat = [[randint(1,99) for i in xrange(mat_size)] for i in xrange(mat_size)]
for line in mat:
for col in line:
print "%2d " % col,
print
print "number of processors: ", nproc
perfect = float(sum(sum(x) for x in mat)) / nproc
print "perfect load (without constraints):", perfect
proc_rects = solve(mat, nproc)
for p in proc_rects:
print p

Publicité

dividee

et l'output des tests (il y a pour chaque CPU, d'abord sa charge puis le rectangle dont il s'occupe)

Example 1
[(9, (1, 3, 3, 3)), (9, (1, 1, 3, 2))]
Example 2
[(8, (3, 1, 4, 4)), (8, (1, 1, 2, 4))]
Example 3
[(121, (4, 1, 4, 2)), (12, (1, 1, 3, 4)), (2, (4, 3, 4, 4))]
Example 4
[(122, (5, 3, 5, 5)), (10, (3, 1, 4, 5)), (10, (1, 1, 2, 5)), (2, (5, 1, 5, 2))]
Example 5
[(122, (1, 1, 1, 3)), (6, (2, 1, 3, 3))]

A more complex example
84 76 42 26 51 41 78 31 48 58 90 50 28 75 62 25 91 98 81 90
31 73 89 68 47 10 43 61 91 96 48 86 26 80 55 2 72 40 82 67
1 49 86 25 33 87 19 57 24 96 80 45 8 32 51 93 11 55 70 55
81 54 96 60 59 45 60 39 57 29 19 19 61 66 48 9 76 87 92 84
89 92 54 39 70 28 81 85 89 59 95 58 45 66 99 91 79 9 61 49
63 84 25 73 12 22 79 33 81 10 15 70 5 57 91 53 68 3 63 61
58 39 37 98 4 3 96 19 13 21 80 93 3 43 11 26 22 65 35 18
50 4 10 98 20 36 73 83 91 17 67 96 6 67 84 34 25 60 44 18
47 41 57 51 31 36 83 25 56 2 74 34 5 28 24 95 35 29 36 94
63 62 71 39 42 65 1 20 34 24 64 38 87 57 42 40 70 42 66 5
45 26 16 53 49 56 75 88 49 31 47 81 87 81 19 99 63 9 72 98
40 68 32 22 72 1 82 53 10 12 65 87 28 97 10 85 40 9 28 45
79 86 14 52 65 35 87 28 2 5 68 56 94 93 91 5 75 70 65 71
90 64 37 54 21 59 1 15 34 79 72 34 62 5 17 98 29 40 55 30
48 24 5 18 52 8 40 33 42 10 90 47 84 97 35 48 70 43 30 73
89 92 63 38 97 64 7 9 75 7 1 39 52 45 49 58 68 42 37 98
26 77 43 36 7 86 70 90 45 68 12 40 21 5 94 22 15 20 38 55
15 98 98 15 41 68 87 50 91 32 50 50 67 20 61 22 34 96 90 81
4 15 26 78 84 58 72 80 7 9 87 4 23 5 2 84 33 16 15 65
96 50 90 50 57 68 80 76 99 74 90 21 54 60 82 48 79 39 59 85
number of processors: 20
perfect load (without constraints): 1027.6
(1122, (4, 15, 10, 17))
(1100, (1, 15, 3, 20))
(1099, (16, 1, 20, 4))
(1077, (1, 11, 5, 14))
(1066, (1, 7, 10, 8))
(1065, (16, 17, 20, 20))
(1062, (7, 1, 10, 6))
(1052, (16, 8, 20, 11))
(1046, (4, 1, 6, 6))
(1038, (11, 12, 12, 20))
(1028, (16, 12, 20, 16))
(1021, (4, 18, 10, 20))
(1015, (13, 1, 15, 8))
(996, (1, 9, 10, 10))
(992, (11, 1, 12, 11))
(989, (6, 11, 10, 14))
(974, (13, 9, 15, 14))
(946, (16, 5, 20, 7))
(945, (13, 15, 15, 20))
(919, (1, 1, 3, 6))

xiluoc

un pc pour les unirs ....

convertion c++ reussi =) 200 lignes, vive python.
par contre 22.5 s en python
et 3 a peine en c++ ?!
je comprend pas.
voila le code

Code :

#include <iostream>
#include <vector>
#include <stdio.h>
using namespace std;
struct Rect {
int rowTop;
int colLeft;
int rowDown;
int colRight;
};
vector <Rect> subRectV;
vector <Rect>::iterator it;
void solve (int procNbr, int startRow, int startCol, int endRow, int endCol);
void partition (Rect R , float ratio, Rect & r1, Rect & r2);
int sum_rect(Rect R);
int **matrix = NULL;
int main()
{
int procNbr, rowSize, colSize;
//get the numbers of proccesors
cout << "Enter the number of processors that need to share the load: ";
///cin >> procNbr;
//get the size of the matrix
cout << "Enter the number of rows and columns of the matrix of the loads: ";
//cin >> rowSize >> colSize;
//create the matrix dynamicaly
rowSize =1000;
colSize = 1000;
//Allocate an array of size rowSize.
matrix = new int*[rowSize];
//Loop through all integer pointers and allocate each one an array of size colSize.
for (int i = 0; i < rowSize; i++)
matrix[i] = new int[colSize];
//Input the values of the matrix
cout << "\nEnter the load matrix (row by row, left to right): \n";
//for (int i=0; i < rowSize; i++)
//for (int j=0; j < colSize; j++)
//cin >> matrix[i][j];
//cout << "\nThe maximum load (first line) followed by\nthe 2 regions selected are (top row, left column, bottom row, right column):"<< endl;
for (int i = 0; i < rowSize; i++) {
for (int j = 0; j < colSize; j++) {
matrix[i][j] = (rand()%999)+1;
}
}
procNbr = 10000;
clock_t start, finish;
long int duration;
start = clock ();
solve (procNbr, 1, 1, rowSize , colSize);
int maxLoad = 0;
cout << "The maximum load (first line) followed by\nthe " << procNbr
<< " regions selected are (top row, left column, bottom row, right column):" << endl;
for (it = subRectV.begin() ; it != subRectV.end(); it++) {
int load = sum_rect(*it);
if (load > maxLoad) { maxLoad = load; }
}
cout << maxLoad << endl;
finish = clock ();
duration = finish - start;
printf ("Actual:%ld\n", duration);
Rect r;
r.rowTop = 1;
r.colLeft = 1;
r.rowDown = rowSize;
r.colRight = colSize;
cout << "perfect : " << sum_rect(r)/procNbr << endl;
//for (it = subRectV.begin() ; it != subRectV.end(); it++) {
// cout << it->rowTop -1 << " " << it->colLeft -1<< " " << it->rowDown -1<< " " << it->colRight -1 << endl;
//}
//finish, free memory
for (int i = 0; i < rowSize; i++)
delete[] matrix[i];
delete[] matrix;
matrix = NULL;
return 0;
}
void solve (int procNbr, int startRow, int startCol, int endRow, int endCol)
{
if (procNbr == 1) {
Rect rTmp;
rTmp.rowTop = startRow;
rTmp.colLeft = startCol;
rTmp.rowDown = endRow;
rTmp.colRight = endCol;
subRectV.push_back(rTmp);
}
else {
int half_procNbr = procNbr / 2;
float ratio = (float) (procNbr - half_procNbr) / half_procNbr;
Rect r1, r2;
Rect R;
R.rowTop = startRow;
R.colLeft = startCol;
R.rowDown = endRow;
R.colRight = endCol;
partition(R, ratio, r1, r2);
solve(procNbr - half_procNbr, r1.rowTop, r1.colLeft , r1.rowDown , r1.colRight);
solve(half_procNbr , r2.rowTop , r2.colLeft , r2.rowDown , r2.colRight );
}
}
void partition (Rect R, float ratio, Rect & best_r1, Rect & best_r2)
{
float r;
int sum1 = 0;
int sum2 = 0;
float best_diff = 1e100; // some big float
int top = R.rowTop;
int left = R.colLeft;
int bottom = R.rowDown;
int right = R.colRight;
int whole_rect_sum = sum_rect(R);
// split by lines
sum1 = 0;
//n-1 rows of possible combinations
for (int split = top ; split < bottom ; split++) {
Rect r1;
r1.rowTop = top;
r1.colLeft = left;
r1.rowDown = split;
r1.colRight = right;
Rect r2;
r2.rowTop = split+1;
r2.colLeft = left;
r2.rowDown = bottom;
r2.colRight = right;
Rect rTmp;
rTmp.rowTop = split;
rTmp.colLeft = left;
rTmp.rowDown = split;
rTmp.colRight = right;
sum1 += sum_rect(rTmp);
sum2 = whole_rect_sum - sum1;
if (sum1 < sum2) {
swap(r1, r2);
r = float(sum2)/sum1;
}
else {
r = float(sum1)/sum2;
}
if (abs(r-ratio) < best_diff) {
best_diff = abs(r-ratio);
best_r1 = r1;
best_r2 = r2;
}
}
// split by columns
sum1 = 0;
//m-1 cols of possible combinations
for (int split = left ; split < right ; split++) {
Rect r1;
r1.rowTop = top;
r1.colLeft = left;
r1.rowDown = bottom;
r1.colRight = split;
Rect r2;
r2.rowTop = top;
r2.colLeft = split+1;
r2.rowDown = bottom;
r2.colRight = right;
Rect rTmp;
rTmp.rowTop = top;
rTmp.colLeft = split;
rTmp.rowDown = bottom;
rTmp.colRight = split;
sum1 += sum_rect(rTmp);
sum2 = whole_rect_sum - sum1;
if (sum1 < sum2) {
swap(r1, r2);
r = float(sum2)/sum1;
}
else {
r = float(sum1)/sum2;
}
if (abs(r-ratio) < best_diff) {
best_diff = abs(r-ratio);
best_r1 = r1;
best_r2 = r2;
}
}
}
int sum_rect(Rect R)
{
int sum=0;
int top = R.rowTop;
int left = R.colLeft;
int bottom = R.rowDown;
int right = R.colRight;
for (int i= top-1; i < bottom ; i++) {
for (int j= left-1; j < right ; j++) {
sum += matrix[i][j];
}
}
return sum;
}

Message édité par xiluoc le 10-08-2005 à 10:58:29

dividee

xiluoc a écrit :

convertion c++ reussi =) 200 lignes, vive python.
par contre 22.5 s en python
et 3 a peine en c++ ?!
je comprend pas.

Qu'est-ce que ça a d'étonnant ? Entre un langage dynamiquement typé et essentiellement interprété, et un langage statiquement typé et compilé (et pour lequel les compilateurs ont une certaine maturité), ça me parait tout à fait crédible comme ordre de grandeur...

FORUM HardWare.fr

Programmation

Algo

Repartition decpu load "decoupe de rectangle", et C++

Sujets relatifs
[c#] declarer la connection avant le page load	pb avec "load data infile"
[GD] Rendre une image transparente + ajout d'un rectangle.	Ajouter un certain nombre de composants lors du load de l'etat
opengl, rectangle contour / couleur de remplissage	Cmt savoir si PHP a bien load MySQL ?!
[Algo][Java] Optimiser la répartition d'un algo	Decoupe d une image
Font / GlyphVector : étirer une chaîne dans un rectangle	les ETL (extract, transform and load)
Plus de sujets relatifs à : Repartition decpu load "decoupe de rectangle", et C++

Page générée en 0.148 secondes