Abstract-Problemet med matrispartitionering för parallell matris-matris multiplikation på heterogena processorer har studerats i stor utsträckning sedan mitten av 1990-talet. Under denna tid, tidigare forskning fokuserade främst på utformningen av effektiv partitionering algoritmer, optimalt eller suboptimalt partitionera matriser i rektanglar. Optimaliteten av den rektangulära partitioneringsformen i sig har aldrig studerats eller ens allvarligt ifrågasatts. Den accepterade metoden är att beaktandet av icke-rektangulära former inte kommer att avsevärt förbättra optimaliteten av lösningen, men kan avsevärt komplicera delningsproblemet, som redan är NPfullständig även för det begränsade fallet av rektangulära former. Det finns dock ingen publicerad forskning som stöder detta tillvägagångssätt. Formen på den globalt optimala partitionen, och hur den bästa rektangulära partitionen jämförs med denna globala optimal, är fortfarande breda öppna problem. Lösning av dessa problem kommer att avgöra om nya partitioneringsalgoritmer som söker efter verkligt optimala, och inte nödvändigtvis rektangulära, lösningar behövs. Detta dokument presenterar de första resultaten av vår forskning om problemet med optimala partitionering former för parallell matrisatrix multiplikation på heterogena processorer. Nämligen studeras fallet med två sammankopplade processorer utförligt. Vi bevisar att beroende på processorers prestandaegenskaper och kommunikationslänken kommer den globalt optimala partitioneringen att ha en av bara två väldefinierade former, av vilka den ena är rektangulär och den andra är icke-rektangelformad. Den teoretiska analysen utförs med hjälp av en ursprunglig matematisk teknik som föreslås i papperet. Det visas att tekniken också kan användas när det gäller godtyckligt antal processorer. Även om omfattande analys av fall av tre och fler processorer är mer komplicerat och ämnet för framtida arbete, papperet bevisar optimaliteten av vissa särskilda icke-rektangulära uppdelning former för vissa kombinationer av prestanda egenskaper heterogena processorer och kommunikationslänkar. Papperet presenterar också experimentella resultat som visar att den optimala icke-rektangulära partitioneringen avsevärt kan överträffa den optimala rektangulära på verkliga heterogena HPC-plattformar.
I REF visades det att när det gäller två resurser är den optimala uppdelningen för alla effektförhållanden av en av två former, en rektangulär och en icke-rektangelformad.
Partitioning for Parallel Matrix-Matrix Multiplication with Heterogeneous Processors: The Optimal Solution
{'venue': '2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum', 'journal': '2012 IEEE 26th International Parallel and Distributed Processing Symposium Workshops & PhD Forum', 'mag_field_of_study': ['Computer Science']}