Problem 921. REPMAT Enhancement - Faster for Large Row Replication of Vector

Created by Richard Zapor

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The Challenge is to modify repmat.m to maintain all of its normal functionality and enhance its performance for large row replication for both N=1 and N&gt;1 cases, B=repmat(A,M,N). The size of A for enhancement cases is [1,n].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For cases of M&gt; 12,288,000 and n&lt;128 or N*n&lt;256 it is possible to perform an enhanced repmat in 40% of the time of repmat. The standard repmat takes 150% longer than repmatLV in certain cases on Cody (2.5 sec / 1 sec).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Input:</w:t></w:r><w:r><w:t> [A,M,N] standard input for repmat</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>A: Vector (row or column) or an array</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>M: row duplication factor of A</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>N: column replication factor of A</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Output:</w:t></w:r><w:r><w:t> B, Array of size [M*m,N*n] where [m,n]=size(A)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Score:</w:t></w:r><w:r><w:t> Performance is based upon time(msec) to execute four large row replications</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Test Cases include normal arrays for which the function must still maintain repmat capability and also the large test cases:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>1: r [1,12] of uint32, M=6144000, N=4</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>2: r [1,12] of uint8, M=6144000, N=16</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>3: r [1,48] of uint32, M=6144000, N=1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>4: r [1,48] of uint8, M=12288000, N=1</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Test cases are sized to not hit the memory limit and clears are implemented.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Potential Path:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>I suggest replicating repmat.m to a local folder and name it repmatLV.m. Create a shell that calls repmatLV as if it was repmat. Implement calls of the stressing test cases from the shell. Use the Profiler Tool to analyze where time is being consumed and devise alternative speed enhancements.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>command window; open repmat</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>file: save as: to local folder with new name</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Create Shell calling function</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>From the Editor/Shell; Tools: Open Profiler</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>From Profiler Window: Start Profiling (Fourth row top left)</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>Explore the results of the profiler windows</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: The above cases assume a 3GB system or better. Reduce M as necessary.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The overall goal of this challenge is to show that matlab built-in functions are excellent resources for methods, optimization of functions is possible depending on individual needs, and profiling is fun.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A follow-up Challenge will demonstrate an optimization of ismember, for the 'sortrows' option with many rows, when both arrays have many rows vs columns and have low commonality(&lt; 10%). Processing time can be reduced by more than 90% for these large row dominant arrays compared to the standard ismember time.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Enjoy.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

The Challenge is to modify repmat.m to maintain all of its normal functionality and enhance its performance for large row replication for both N=1 and N>1 cases,
B=repmat(A,M,N). The size of A for enhancement cases is [1,n].For cases of M> 12,288,000 and n&lt;128 or N*n&lt;256 it is possible to perform an enhanced repmat in 40% of the time of repmat. The standard repmat takes 150% longer than repmatLV in certain cases on Cody (2.5 sec / 1 sec).Input: [A,M,N] standard input for repmat<ul><li>A: Vector (row or column) or an array</li><li>M: row duplication factor of A</li><li>N: column replication factor of A</li></ul>Output: B, Array of size [M*m,N*n] where [m,n]=size(A)Score: Performance is based upon time(msec) to execute four large row replicationsTest Cases include normal arrays for which the function must still maintain repmat capability and also the large test cases:<ul><li>1: r [1,12] of uint32, M=6144000, N=4</li><li>2: r [1,12] of uint8, M=6144000, N=16</li><li>3: r [1,48] of uint32, M=6144000, N=1</li><li>4: r [1,48] of uint8, M=12288000, N=1</li><li>Test cases are sized to not hit the memory limit and clears are implemented.</li></ul>Potential Path:I suggest replicating repmat.m to a local folder and name it repmatLV.m. Create a shell that calls repmatLV as if it was repmat. Implement calls of the stressing test cases from the shell. Use the Profiler Tool to analyze where time is being consumed and devise alternative speed enhancements.<ol><li>command window; open repmat</li><li>file: save as: to local folder with new name</li><li>Create Shell calling function</li><li>From the Editor/Shell; Tools: Open Profiler</li><li>From Profiler Window: Start Profiling (Fourth row top left)</li><li>Explore the results of the profiler windows</li></ol>Note: The above cases assume a 3GB system or better. Reduce M as necessary.The overall goal of this challenge is to show that matlab built-in functions are excellent resources for methods, optimization of functions is possible depending on individual needs, and profiling is fun.A follow-up Challenge will demonstrate an optimization of ismember, for the 'sortrows' option with many rows, when both arrays have many rows vs columns and have low commonality(&lt; 10%). Processing time can be reduced by more than 90% for these large row dominant arrays compared to the standard ismember time.Enjoy.

Solve

Solution Stats

18 Solutions
10 Solvers

Last Solution submitted on Sep 08, 2015

Last 200 Solutions

Problem Recent Solvers10

Problem Tags

Problem 921. REPMAT Enhancement - Faster for Large Row Replication of Vector

Solution Stats

Last 200 Solutions

Problem Recent Solvers10

Suggested Problems

More from this Author236

Problem Tags

Problem 921. REPMAT Enhancement - Faster for Large Row Replication of Vector

Solution Stats

Last 200 Solutions

Problem Recent Solvers10

Suggested Problems

More from this Author236

Problem Tags

Players