Mixing
Amount of integer multiplications performed with matrices - how much faster?
$begingroup$
I am trying to determine how much faster a multiprocessing system would be at multiplying matrices than a single processor system.
Here is my thought process/example:
Assume Matrix A is k x l and Matrix B is l x m.
The matrix product of AB is k x m matrix C
Every entry in matrix C is a scalar product which requires l multiplications (and l - 1 additions).
In a single processor system, this would require l x km number of entries.
In a multiprocessing system with km processors(where all of this would be done in parallel), this would only require l integer multiplications.
To me, this means that the multiprocessing system is km times faster. Is this correct, or is there more to it than that?
linear-algebra matrices
asked Jan 8 at 23:44
whitsondai whitsondai
12
$endgroup$
add a comment |
$begingroup$
I am trying to determine how much faster a multiprocessing system would be at multiplying matrices than a single processor system.
Here is my thought process/example:
Assume Matrix A is k x l and Matrix B is l x m.
The matrix product of AB is k x m matrix C
Every entry in matrix C is a scalar product which requires l multiplications (and l - 1 additions).
In a single processor system, this would require l x km number of entries.
In a multiprocessing system with km processors(where all of this would be done in parallel), this would only require l integer multiplications.
To me, this means that the multiprocessing system is km times faster. Is this correct, or is there more to it than that?
linear-algebra matrices
asked Jan 8 at 23:44
whitsondai whitsondai
12
$endgroup$
1
$begingroup$
You need to tell us how many processors your multiprocessing system has! (Also, each entry in $C$ requires $l$ multiplications, not $l^2$.)
$endgroup$
– TonyK
Jan 8 at 23:48
$begingroup$
Oops -- the multiprocessing system has km processors
$endgroup$
– whitsondai
Jan 8 at 23:50
$begingroup$
Then you should edit that information into your question. (And fix the $ltimes l$ problem while you're at it.)
$endgroup$
– TonyK
Jan 9 at 0:08
$begingroup$
thanks, it has been updated
$endgroup$
– whitsondai
Jan 9 at 1:03
add a comment |
$begingroup$
I am trying to determine how much faster a multiprocessing system would be at multiplying matrices than a single processor system.
Here is my thought process/example:
Assume Matrix A is k x l and Matrix B is l x m.
The matrix product of AB is k x m matrix C
Every entry in matrix C is a scalar product which requires l multiplications (and l - 1 additions).
In a single processor system, this would require l x km number of entries.
In a multiprocessing system with km processors(where all of this would be done in parallel), this would only require l integer multiplications.
To me, this means that the multiprocessing system is km times faster. Is this correct, or is there more to it than that?
linear-algebra matrices
asked Jan 8 at 23:44
whitsondai whitsondai
12
$endgroup$
I am trying to determine how much faster a multiprocessing system would be at multiplying matrices than a single processor system.
Here is my thought process/example:
Assume Matrix A is k x l and Matrix B is l x m.
The matrix product of AB is k x m matrix C
Every entry in matrix C is a scalar product which requires l multiplications (and l - 1 additions).
In a single processor system, this would require l x km number of entries.
In a multiprocessing system with km processors(where all of this would be done in parallel), this would only require l integer multiplications.
To me, this means that the multiprocessing system is km times faster. Is this correct, or is there more to it than that?
linear-algebra matrices
linear-algebra matrices
asked Jan 8 at 23:44
whitsondai whitsondai
12
asked Jan 8 at 23:44
whitsondai whitsondai
12
edited Jan 9 at 1:02
whitsondai
asked Jan 8 at 23:44
whitsondai whitsondai
12
asked Jan 8 at 23:44
whitsondai whitsondai
12
asked Jan 8 at 23:44
whitsondai whitsondai
12
12
1
$begingroup$
You need to tell us how many processors your multiprocessing system has! (Also, each entry in $C$ requires $l$ multiplications, not $l^2$.)
$endgroup$
– TonyK
Jan 8 at 23:48
$begingroup$
Oops -- the multiprocessing system has km processors
$endgroup$
– whitsondai
Jan 8 at 23:50
$begingroup$
Then you should edit that information into your question. (And fix the $ltimes l$ problem while you're at it.)
$endgroup$
– TonyK
Jan 9 at 0:08
$begingroup$
thanks, it has been updated
$endgroup$
– whitsondai
Jan 9 at 1:03
add a comment |
1
$begingroup$
You need to tell us how many processors your multiprocessing system has! (Also, each entry in $C$ requires $l$ multiplications, not $l^2$.)
$endgroup$
– TonyK
Jan 8 at 23:48
$begingroup$
Oops -- the multiprocessing system has km processors
$endgroup$
– whitsondai
Jan 8 at 23:50
$begingroup$
Then you should edit that information into your question. (And fix the $ltimes l$ problem while you're at it.)
$endgroup$
– TonyK
Jan 9 at 0:08
$begingroup$
thanks, it has been updated
$endgroup$
– whitsondai
Jan 9 at 1:03
1
1
$begingroup$
You need to tell us how many processors your multiprocessing system has! (Also, each entry in $C$ requires $l$ multiplications, not $l^2$.)
$endgroup$
– TonyK
Jan 8 at 23:48
$begingroup$
You need to tell us how many processors your multiprocessing system has! (Also, each entry in $C$ requires $l$ multiplications, not $l^2$.)
$endgroup$
– TonyK
Jan 8 at 23:48
$begingroup$
Oops -- the multiprocessing system has km processors
$endgroup$
– whitsondai
Jan 8 at 23:50
$begingroup$
Oops -- the multiprocessing system has km processors
$endgroup$
– whitsondai
Jan 8 at 23:50
$begingroup$
Then you should edit that information into your question. (And fix the $ltimes l$ problem while you're at it.)
$endgroup$
– TonyK
Jan 9 at 0:08
$begingroup$
Then you should edit that information into your question. (And fix the $ltimes l$ problem while you're at it.)
$endgroup$
– TonyK
Jan 9 at 0:08
$begingroup$
thanks, it has been updated
$endgroup$
– whitsondai
Jan 9 at 1:03
$begingroup$
thanks, it has been updated
$endgroup$
– whitsondai
Jan 9 at 1:03
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As long as you have at least $km$ processors you are (roughly) right, depending on the time it takes to assemble the results from all the processors. You have $km$ entries in the result to compute and you could have each processor compute one of them. If you want all the results in a single array on one processor you need to communicate with it. How that compares timewise with the multiplications depends very much on your system.
If you have $2km$ processors you could imagine sharing one result entry across two processors. Each one would do half the multiplies and adds, then one of them would do the final addition.
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066875%2famount-of-integer-multiplications-performed-with-matrices-how-much-faster%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
As long as you have at least $km$ processors you are (roughly) right, depending on the time it takes to assemble the results from all the processors. You have $km$ entries in the result to compute and you could have each processor compute one of them. If you want all the results in a single array on one processor you need to communicate with it. How that compares timewise with the multiplications depends very much on your system.
If you have $2km$ processors you could imagine sharing one result entry across two processors. Each one would do half the multiplies and adds, then one of them would do the final addition.
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
$endgroup$
add a comment |
$begingroup$
As long as you have at least $km$ processors you are (roughly) right, depending on the time it takes to assemble the results from all the processors. You have $km$ entries in the result to compute and you could have each processor compute one of them. If you want all the results in a single array on one processor you need to communicate with it. How that compares timewise with the multiplications depends very much on your system.
If you have $2km$ processors you could imagine sharing one result entry across two processors. Each one would do half the multiplies and adds, then one of them would do the final addition.
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
$endgroup$
add a comment |
$begingroup$
As long as you have at least $km$ processors you are (roughly) right, depending on the time it takes to assemble the results from all the processors. You have $km$ entries in the result to compute and you could have each processor compute one of them. If you want all the results in a single array on one processor you need to communicate with it. How that compares timewise with the multiplications depends very much on your system.
If you have $2km$ processors you could imagine sharing one result entry across two processors. Each one would do half the multiplies and adds, then one of them would do the final addition.
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
$endgroup$
As long as you have at least $km$ processors you are (roughly) right, depending on the time it takes to assemble the results from all the processors. You have $km$ entries in the result to compute and you could have each processor compute one of them. If you want all the results in a single array on one processor you need to communicate with it. How that compares timewise with the multiplications depends very much on your system.
If you have $2km$ processors you could imagine sharing one result entry across two processors. Each one would do half the multiplies and adds, then one of them would do the final addition.
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
answered Jan 9 at 1:42
Ross MillikanRoss Millikan
294k23198371
294k23198371
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3066875%2famount-of-integer-multiplications-performed-with-matrices-how-much-faster%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
You need to tell us how many processors your multiprocessing system has! (Also, each entry in $C$ requires $l$ multiplications, not $l^2$.)
$endgroup$
– TonyK
Jan 8 at 23:48
$begingroup$
Oops -- the multiprocessing system has km processors
$endgroup$
– whitsondai
Jan 8 at 23:50
$begingroup$
Then you should edit that information into your question. (And fix the $ltimes l$ problem while you're at it.)
$endgroup$
– TonyK
Jan 9 at 0:08
$begingroup$
thanks, it has been updated
$endgroup$
– whitsondai
Jan 9 at 1:03