ضرب ماتریس 4x4

[Ananas]

سلام به همه ی دوستای خوب.
من بلد نیستم به زبان اسمبلی برنامه بنویسیم و می خواستم لطف کنین و نظرتون رو راجب سرعت اجرای یک تابع که به زبان اسمبلی نوشته بشه بدونم.
توابعی هست تو dll های دایرکت ایکس براب ضرب ماتریس 4x4 که سرعتش تقریبا 4 برابر تابعی هست که من خودم با c++ مینویسم. ساختار ماتریس به این شکله :

typedef struct _D3DMATRIX {
union {
struct {
float _11, _12, _13, _14;
float _21, _22, _23, _24;
float _31, _32, _33, _34;
float _41, _42, _43, _44;

};
float m[4][4];
};
} D3DMATRIX;

16 تا عدد اعشاری 32 بیتی.
ضربی که تو dll دایرکت ایکسه به این شکل هست :

// Matrix multiplication. The result represents the transformation M2
// followed by the transformation M1. (Out = M1 * M2)
D3DXMATRIX* WINAPI D3DXMatrixMultiply
( D3DXMATRIX *pOut, CONST D3DXMATRIX *pM1, CONST D3DXMATRIX *pM2 );

ضربی که من نوشتم :

void M4DMultiply(TMatrix4D & mOut, const TMatrix4D & m1, const TMatrix4D & m2)
{
mOut._11 = m1._11 * m2._11 + m1._12 * m2._21 + m1._13 * m2._31 + m1._14 * m2._41;
mOut._12 = m1._11 * m2._12 + m1._12 * m2._22 + m1._13 * m2._32 + m1._14 * m2._42;
mOut._13 = m1._11 * m2._13 + m1._12 * m2._23 + m1._13 * m2._33 + m1._14 * m2._43;
mOut._14 = m1._11 * m2._14 + m1._12 * m2._24 + m1._13 * m2._34 + m1._14 * m2._44;

mOut._21 = m1._21 * m2._11 + m1._22 * m2._21 + m1._23 * m2._31 + m1._24 * m2._41;
mOut._22 = m1._21 * m2._12 + m1._22 * m2._22 + m1._23 * m2._32 + m1._24 * m2._42;
mOut._23 = m1._21 * m2._13 + m1._22 * m2._23 + m1._23 * m2._33 + m1._24 * m2._43;
mOut._24 = m1._21 * m2._14 + m1._22 * m2._24 + m1._23 * m2._34 + m1._24 * m2._44;

mOut._31 = m1._31 * m2._11 + m1._32 * m2._21 + m1._33 * m2._31 + m1._34 * m2._41;
mOut._32 = m1._31 * m2._12 + m1._32 * m2._22 + m1._33 * m2._32 + m1._34 * m2._42;
mOut._33 = m1._31 * m2._13 + m1._32 * m2._23 + m1._33 * m2._33 + m1._34 * m2._43;
mOut._34 = m1._31 * m2._14 + m1._32 * m2._24 + m1._33 * m2._34 + m1._34 * m2._44;

mOut._41 = m1._41 * m2._11 + m1._42 * m2._21 + m1._43 * m2._31 + m1._44 * m2._41;
mOut._42 = m1._41 * m2._12 + m1._42 * m2._22 + m1._43 * m2._32 + m1._44 * m2._42;
mOut._43 = m1._41 * m2._13 + m1._42 * m2._23 + m1._43 * m2._33 + m1._44 * m2._43;
mOut._44 = m1._41 * m2._14 + m1._42 * m2._24 + m1._43 * m2._34 + m1._44 * m2._44;
}

به نظر شما اگه این تابع با اسمبلی نوشته بشه سرعتش به چهار برابر میرسه یعنی در حد تابع DirectX ؟
البته من این تابع با روش های مختلف ورودی و خروجی تابع امتحان کردم و به نظرم این تقریبا سریع ترین حالتی هست که به زبان c++ میشه نوشت.

[xman_1365_x]

بدنه تابع D3DXMatrixMultiply رو قرار بدین اگر دسترسی ندارین باید با ida و یا ollydbg متوجه درون تابع بشین تا بشه مقایسه کرد.
برای optimize کتاب زبان اسمبلی پیشرفته - بحرینی را مطالعه کنید.

[Ananas]

خیلی ممنون. متشکر از راهنمایی و هم معرفی کتاب.
ولی من جواب سوالمو هنوز نگرفتم. تابع D3DXMatrixMultiply داخل d3dx9.dll و dll هایی با اسم مشابه هست. منظورتون از بدنه ی تابع سورس عملیات ضرب هست؟ خوب اگه داشتم که دیگه زحمت دوستان نمی دادم. اگه منظورتون طریقه ی نوشتن و ورودی و خروجی هست تو پست قبلی نوشتم قبل از تابع خودم. ida و یا ollydbg رو کار نکردم و بیشتر سوالم اینه که ارزش نوشتن به assembly رو داره؟ یعنی اگه با اسمبلی زور بزنم یاد بگیرم بنویسم سرعتش میتونه با تابع دایرکت ایکس برابری کنه؟ یا بهتر بگم کار به دایرکت ایکس نداشته باشیم تابع بالا که خودم نوشتم و سورسشو شما ملاحظه میکنید رو داریم، حالا اگه این ضرب و جمع ها و مساوی قرار دادن ها رو با زبان اسمبلی به شکل این لاین تو کد C++‎ بنویسیم سرعتش ممکنه تا چه حدی بالا بره؟ مثلا 2 برابر ؟ یا سه برابر ؟ یا 4 ... ؟ اگه امکان داره لطف کنین به عنوان نمونه یک یا دو خط از کد رو مثلا :


mOut._11 = m1._11 * m2._11 + m1._12 * m2._21 + m1._13 * m2._31 + m1._14 * m2._41;mOut._12 = m1._11 * m2._12 + m1._12 * m2._22 + m1._13 * m2._32 + m1._14 * m2._42;


قسمت رو به شکل اسمبلی بنویسید سعی میکنم خودم بقیشو از روی کد شما کامل کنم و امتحانش کنم و اگه اشکال پیش اومد ازتون می پرسم. ممنون میشم اگه لطف کنین.
البته فقط این تابع نیست و توابع بیشتری هست که من می خوام خیلیاشونو به دلیل استفاده نکردن از dll دایرکت ایکس خودم بنویسمشون (نوشتم ولی این دفعه به شکل اسمبلی و سریع تر) حالا اگه راهنمایی کنین که با اعداد اعشاری 32 بیتی (float) چطور کد اسمبلی رو شروع کنم. اگه یک مثال باشه سعی میکنم بقیشو خودم ادامه بدم.
ممنون.

[xman_1365_x]

تابع D3DXMatrixMultiply داخل d3dx9.dll و dll هایی با اسم مشابه هست. منظورتون از بدنه ی تابع سورس عملیات ضرب هست؟
برای دسترسی به بدنه این تابع نیاز به استفاده از ابزار ida,ollydbg هست.


به نظر شما اگه این تابع با اسمبلی نوشته بشه سرعتش به چهار برابر میرسه یعنی در حد تابع DirectX ؟
و

بیشتر سوالم اینه که ارزش نوشتن به assembly رو داره؟یعنی اگه با اسمبلی زور بزنم یاد بگیرم بنویسم سرعتش میتونه با تابع دایرکت ایکس برابری کنه؟
لزوما خیر ، برای سرعت اجرا عوامل زیادی هست از پردازنده گرفته تا کامپایلر و سطح optimize کامپایلر و یک عامل مهم الگوریتم شما هست ، حالا اگر همه این مراحل بهینه شد شما میتونید کد رو در موارد بحرانی با اسمبلی optimize تر کنید چراکه جدیدترین کامپایلر ها هم نمیتونند بخوبی کد رو بهینه کنند.
و کتاب های زیادی برای این امر نوشته شده که باید مطالعه کنید. اگر کد شما در اسمبلی بدرستی نوشته نشه میتونه کندتر هم بشه


البته من این تابع با روش های مختلف ورودی و خروجی تابع امتحان کردم و به نظرم این تقریبا سریع ترین حالتی هست که به زبان C++‎‎‎‎‎ میشه نوشت.
این مورد رو باید جستجو کنید برای الگوریتم بهینه و یا در صورت امکان ساده سازی تابع


اگه این ضرب و جمع ها و مساوی قرار دادن ها رو با زبان اسمبلی به شکل این لاین تو کد C++‎‎‎‎‎‎ بنویسیم سرعتش ممکنه تا چه حدی بالا بره؟ مثلا 2 برابر ؟ یا سه برابر ؟ یا 4 ... ؟
این موارد نیاز به تحلیل داره که ببنید کامپایلر چه کدی به شما میده و بعد کد رو در صورت امکان با اسمبلی بهینه کنید اگرنه کامپایلر هم در نهایت کد ماشین به شما ارائه میده

اگه امکان داره لطف کنین به عنوان نمونه یک یا دو خط از کد رو مثلا :
من یک خط رو با دستورات x87 (http://en.wikipedia.org/wiki/X87) , x86 (http://en.wikipedia.org/wiki/X86_instruction_listings) براتون نوشتم که بررسی نکردم سریع ترین حالت باشه،ضمنا در مورد inline باید یادتون باشه قابلیت حمل رو خراب میکنه مثلا پردازنده arm یا intel8086 این دستورات رو نمیشناسه
پس باید حتی اگر پردازنده شما اینتل یا amd هست توجه کنید که پردازنده این دستورات رو پشتیبانی کنه


void M4DMultiply2(TMatrix4D & mOut, const TMatrix4D & m1, const TMatrix4D & m2)
{
//mOut._11 = (m1._11 * m2._11) + (m1._12 * m2._21) + (m1._13 * m2._31) + (m1._14 * m2._41);
__asm {
mov eax,m1
mov ebx,m2

fld [eax]m1._11 ; Load SPFP 32-bit to 80-bit
fld [ebx]m2._11 ; Load DPFP 64-bit to 80-bit
fmul

fld [eax]m1._12
fld [ebx]m2._21
fmul
fadd

fld [eax]m1._13
fld [ebx]m2._31
fmul
fadd

fld [eax]m1._14
fld [ebx]m2._41
fmul
fadd

mov eax,mOut
fst [eax]mOut._11 ; Save float to memory.
};

}


ویرایش:
بد نیست بعد از کامپایل با vs2010 رو ببینید:


.text:0040105B mov eax, [esp+0D0h+var_CC]
.text:0040105F mov ebx, [esp+0D0h+var_C8]
.text:00401063 fld dword ptr [eax]
.text:00401065 fld dword ptr [ebx]
.text:00401067 fmulp st(1), st
.text:00401069 fld dword ptr [eax+4]
.text:0040106C fld dword ptr [ebx+10h]
.text:0040106F fmulp st(1), st
.text:00401071 faddp st(1), st
.text:00401073 fld dword ptr [eax+8]
.text:00401076 fld dword ptr [ebx+20h]
.text:00401079 fmulp st(1), st
.text:0040107B faddp st(1), st
.text:0040107D fld dword ptr [eax+0Ch]
.text:00401080 fld dword ptr [ebx+30h]
.text:00401083 fmulp st(1), st
.text:00401085 faddp st(1), st
.text:00401087 mov eax, [esp+0D0h+var_C4]
.text:0040108B fst dword ptr [eax]

موفق باشی

[xman_1365_x]

با توجه به پست قبل و برای گرفتن جوابتون همونطور که گفتم باید بهترین حالت رو برای بهینه کردن کد و نوشتن اسمبلی به کار ببرید
همونطور که در کد زیر میبینید کامپایلر برای کد مشابه از دستورات کمتر استفاده کرد که من همونطور که گفتم به بهینه بودنش توجه نکردم،این بهترین پاسخ برای شماست که اگر با اسمبلی بنویسید دلیل بر سرعت بیشتر نیست،بنظر من بهترین روش همون بهینه کردن کد سی هست که نیاز به تسلط کامل به زبان اسمبلی دارد



.text:00401006 fld dword ptr [ecx]
.text:00401008 fmul dword ptr [eax]
.text:0040100A fld dword ptr [ecx+4]
.text:0040100D fmul dword ptr [eax+10h]
.text:00401010 faddp st(1), st
.text:00401012 fld dword ptr [eax+20h]
.text:00401015 fmul dword ptr [ecx+8]
.text:00401018 faddp st(1), st
.text:0040101A fld dword ptr [eax+30h]
.text:0040101D fmul dword ptr [ecx+0Ch]
.text:00401020 faddp st(1), st
.text:00401022 fstp dword ptr [edx]

موفق باشی

[Ananas]

خیلی ممنون.
این کد رو Borland_C++Builder موقع کامپایل ساخته البته من فقط تا خط اول ضرب ماتریسی رو کپی میکنم :


@@M4DMultiply$qr9TMatrix4Drx9TMatrix4Dt2 proc near
?live16392@0:
@41:
push ebp
mov ebp,esp
mov edx,dword ptr [ebp+16]
mov eax,dword ptr [ebp+12]
mov ecx,dword ptr [ebp+8]
?live16392@16: ; EAX = m1, EDX = m2, ECX = mOut
fld dword ptr [eax]
fmul dword ptr [edx]
fld dword ptr [eax+4]
fmul dword ptr [edx+16]
faddp st(1),st
fld dword ptr [eax+8]
fmul dword ptr [edx+32]
faddp st(1),st
fld dword ptr [eax+12]
fmul dword ptr [edx+48]
faddp st(1),st
fstp dword ptr [ecx]

تقریبا همون چیزی هست که VS کامپایل کرده. فکر میکنم از این بهینه تر نشه این کارو انجام داد البته برای یک خط ولی برای 16 مرحله از ضرب ماتریس اگه اشتباه نکنم شاید بشه تو st اعداد رو 4 تا 4 تا و در 4 مرحله وارد رجیستر کرد و لود کردن تکراری از رم جلوگیری بشه.
اما در کل یک احتمال دیگه هم میدم که توابع ماتریسی دایرکت ایکس تو GPU کارت گرافیک محاسبه میشن و به شکل اسمبلی نیستند. اگه اینطور باشه نمیشه به سرعت اون رسید ولی هر چی بتونیم این توابع رو سریعتر بنویسیم بازم بهتره.
من کد شما رو خواستم به شکل اینلاین تو دلفی بنویسم ولی هنوز نتونستم کد رو درست وارد کنم چون انگار دلفی تفاوت هایی داره. من روشون کار میکنم دوباره نتیجه رو اینجا می نویسم انشاالله.

[xman_1365_x]

من کد شما رو خواستم به شکل اینلاین تو دلفی بنویسم ولی هنوز نتونستم کد رو درست وارد کنم چون انگار دلفی تفاوت هایی داره
Delphi Inline Assembly Code (Win32 Only) (http://docs.embarcadero.com/products/rad_studio/delphiAndcpp2009/HelpUpdate2/EN/html/devcommon/inlineassemblycodepart_xml.html)