performance - কেন অযৌক্তিক MOV নির্দেশাবলী x86_64 সমাবেশে একটি টাইট লুপ গতি বাড়ানো হবে?




optimization assembly (3)

পটভূমি:

এমবেডেড সমাবেশ ভাষা সহ কিছু Pascal কোডটি অপ্টিমাইজ করার সময়, আমি একটি অপ্রয়োজনীয় MOV নির্দেশনা লক্ষ্য করেছি এবং এটি সরানো হয়েছে।

আমার অবাক হওয়ার জন্য, অ-প্রয়োজনীয় নির্দেশনা সরানোর ফলে আমার প্রোগ্রামটি হ্রাস পায়

আমি নির্বিচারে যোগ যে পাওয়া , নিরর্থক MOV নির্দেশাবলী এমনকি আরও কর্মক্ষমতা বৃদ্ধি

প্রভাব অনিশ্চিত এবং সঞ্চালনের আদেশের উপর ভিত্তি করে পরিবর্তন: একক লাইন দ্বারা আপ বা ডাউন ট্রান্সফার একই জাঙ্ক নির্দেশগুলি একটি মন্দা উত্পাদন করে

আমি বুঝতে পারছি যে সিপিইউ সমস্ত ধরণের অপটিমাইজেশন এবং স্ট্রিমলাইনিং করে, কিন্তু, এটি কালো জাদুের মতো বেশি মনে হয়।

তথ্যটি:

আমার কোডের একটি সংস্করণ শর্তসাপেক্ষে একটি লুপের মাঝখানে তিনটি জাঙ্ক অপারেশনগুলিকে কম্পাইল করে যা 2**20==1048576 বার চালায়। (পার্শ্ববর্তী প্রোগ্রাম শুধু SHA-256 হ্যাশ হিসাব করে)।

আমার পরিবর্তে পুরাতন মেশিনের ফলাফল (ইন্টেল (আর) কোর (টিএম) 2 CPU 6400 @ 2.13 গিগাহার্জ):

avg time (ms) with -dJUNKOPS: 1822.84 ms
avg time (ms) without:        1836.44 ms

রান ক্রম এলোমেলোভাবে প্রতিবার পরিবর্তন সঙ্গে, একটি লুপ 25 বার চালানো হয়।

উদ্ধৃতাংশ:

{$asmmode intel}
procedure example_junkop_in_sha256;
  var s1, t2 : uint32;
  begin
    // Here are parts of the SHA-256 algorithm, in Pascal:
    // s0 {r10d} := ror(a, 2) xor ror(a, 13) xor ror(a, 22)
    // s1 {r11d} := ror(e, 6) xor ror(e, 11) xor ror(e, 25)
    // Here is how I translated them (side by side to show symmetry):
  asm
    MOV r8d, a                 ; MOV r9d, e
    ROR r8d, 2                 ; ROR r9d, 6
    MOV r10d, r8d              ; MOV r11d, r9d
    ROR r8d, 11    {13 total}  ; ROR r9d, 5     {11 total}
    XOR r10d, r8d              ; XOR r11d, r9d
    ROR r8d, 9     {22 total}  ; ROR r9d, 14    {25 total}
    XOR r10d, r8d              ; XOR r11d, r9d

    // Here is the extraneous operation that I removed, causing a speedup
    // s1 is the uint32 variable declared at the start of the Pascal code.
    //
    // I had cleaned up the code, so I no longer needed this variable, and 
    // could just leave the value sitting in the r11d register until I needed
    // it again later.
    //
    // Since copying to RAM seemed like a waste, I removed the instruction, 
    // only to discover that the code ran slower without it.
    {$IFDEF JUNKOPS}
    MOV s1,  r11d
    {$ENDIF}

    // The next part of the code just moves on to another part of SHA-256,
    // maj { r12d } := (a and b) xor (a and c) xor (b and c)
    mov r8d,  a
    mov r9d,  b
    mov r13d, r9d // Set aside a copy of b
    and r9d,  r8d

    mov r12d, c
    and r8d, r12d  { a and c }
    xor r9d, r8d

    and r12d, r13d { c and b }
    xor r12d, r9d

    // Copying the calculated value to the same s1 variable is another speedup.
    // As far as I can tell, it doesn't actually matter what register is copied,
    // but moving this line up or down makes a huge difference.
    {$IFDEF JUNKOPS}
    MOV s1,  r9d // after mov r12d, c
    {$ENDIF}

    // And here is where the two calculated values above are actually used:
    // T2 {r12d} := S0 {r10d} + Maj {r12d};
    ADD r12d, r10d
    MOV T2, r12d

  end
end;

এটি নিজে চেষ্টা করো:

আপনি যদি নিজের চেষ্টা করতে চান তবে কোডটি GitHub এ অনলাইন।

আমার প্রশ্নগুলো:

  • কেন RAM এর একটি নিবন্ধের বিষয়বস্তু অননুমোদিতভাবে অনুলিপি করবে কর্মক্ষমতা বৃদ্ধি?
  • কেন একই নিরর্থক নির্দেশ কিছু লাইন একটি গতিপথ প্রদান, এবং অন্যদের উপর একটি মন্দা প্রদান করবে?
  • একটি কম্পাইলার দ্বারা predictably শোষিত হতে পারে যে এই আচরণ কিছু?

ক্যাশে প্রস্তুতি

অপারেশন সরান মেমরি ক্যাশে প্রস্তুত এবং পরবর্তী পদক্ষেপ অপারেশন দ্রুত করতে পারেন। একটি CPU সাধারণত দুটি লোড ইউনিট এবং এক দোকান ইউনিট আছে। একটি লোড ইউনিট মেমরি থেকে একটি নিবন্ধে (একটি চক্র পড়তে পারে) পড়তে পারে, নিবন্ধ থেকে মেমরির একটি স্টোর ইউনিট স্টোর। রেজিস্টারদের মধ্যে অপারেশন করতে অন্যান্য ইউনিট আছে। সব ইউনিট সমান্তরাল কাজ। সুতরাং, প্রতিটি চক্রের উপর, আমরা একযোগে কয়েকটি অপারেশন করতে পারি, কিন্তু দুইটি লোড, এক দোকান এবং বেশ কয়েকটি রেজিস্ট্রেশন অপারেশন। সাধারণত এটি সমান নিবন্ধকের সাথে 4 টি সাধারণ অপারেশন পর্যন্ত, এক্সএমএম / YMM নিবন্ধকের সাথে 3 টি সহজ অপারেশন এবং কোনও নিবন্ধকের সাথে 1-2 টি জটিল ক্রিয়াকলাপ। আপনার কোডটিতে রেজিস্ট্রারের সাথে অনেকগুলি ক্রিয়াকলাপ রয়েছে, তাই একটি ডামি মেমরি স্টোর অপারেশন বিনামূল্যে (যেহেতু 4 টির বেশি নিবন্ধন অপারেশন আছে তবে), তবে পরবর্তী স্টোর ক্রিয়াকলাপের জন্য এটি মেমরি ক্যাশে তৈরি করে। কিভাবে মেমরি স্টোর কাজ করে তা জানতে, Intel 64 এবং IA-32 আর্কিটেকচারের অপ্টিমাইজেশান রেফারেন্স ম্যানুয়াল পড়ুন

মিথ্যা নির্ভরতা ভাঙ্গা

যদিও এটি আপনার ক্ষেত্রে সঠিকভাবে উল্লেখ করে না তবে কখনও কখনও 64-বিট প্রসেসরের (যেমন আপনার ক্ষেত্রে) 32-বিট মুভি ক্রিয়াকলাপ ব্যবহার করে উচ্চ বিটগুলি (32-63) সাফ করে এবং নির্ভরতা শৃঙ্খলগুলি ভেঙ্গে দেয়।

এটি সুপরিচিত যে x86-64 এর অধীনে 32-বিট অপারেডগুলি ব্যবহার করে 64 বিট নিবন্ধের উচ্চ বিটগুলিকে সাফ করে। Pleas প্রাসঙ্গিক বিভাগটি পড়ুন - 3.4.1.1 - Intel® 64 এবং IA-32 আর্কিটেকচারের সফ্টওয়্যার বিকাশকারীর ম্যানুয়াল ভলিউম 1 :

32-বিট অপারেডগুলি একটি 32-বিট ফলাফল জেনারেট করে, গন্তব্য সাধারণ উদ্দেশ্যে নিবন্ধনের 64-বিট ফলাফলের শূন্য-বর্ধিত ফলাফল

সুতরাং, MOV নির্দেশাবলী, যা প্রথম দর্শনে নিরর্থক মনে হতে পারে, যথাযথ নিবন্ধকের উচ্চ বিট সাফ করুন। এটা কি আমাদের দেয়? এটি নির্ভরতা চেইনগুলি ভেঙ্গে দেয় এবং 1995 সালে পেন্টিয়াম প্রো থেকে CPU- র মাধ্যমে অভ্যন্তরীণভাবে বাস্তবায়িত হওয়া আউট-অফ-অর্ডার অ্যালগরিদম অনুসারে, এলোমেলোভাবে এলোমেলোভাবে নির্দেশগুলি কার্যকর করতে দেয়।

Intel® 64 এবং IA-32 আর্কিটেকচারের অপ্টিমাইজেশান রেফারেন্স ম্যানুয়াল থেকে একটি উদ্ধৃতি, বিভাগ 3.5.1.8:

আংশিক নিবন্ধটি সংশোধন করে এমন কোড ক্রমগুলি নির্ভরতা শৃঙ্খলে কিছু বিলম্বের সম্মুখীন হতে পারে, তবে নির্ভরতা ভাঙা আইডিয়ম ব্যবহার করে এড়ানো যেতে পারে। ইনটেল কোর মাইক্রো-আর্কিটেকচারের উপর ভিত্তি করে প্রসেসরগুলিতে, শূন্যে নিবন্ধন সামগ্রী সাফ করার জন্য সফ্টওয়্যার এই নির্দেশাবলী ব্যবহার করে অনেকগুলি নির্দেশ কার্যকর নির্বাহ নির্ভরতা সহায়তা করতে পারে। আংশিক নিবন্ধকের পরিবর্তে 32-বিট নিবন্ধকদের অপারেটিংয়ের মাধ্যমে নির্দেশনার মধ্যে নিবন্ধকের অংশগুলির উপর নির্ভরতাগুলি ভেঙ্গে ফেলুন। প্যাচসমূহের জন্য, এটি 32 বিট প্যাচগুলি বা MOVZX ব্যবহার করে সম্পন্ন করা যেতে পারে।

অ্যাসেম্বলি / কম্পাইলার কোডিং রুল 37. (এম প্রভাব, এমএইচ জেনারেলিটি) : আংশিক নিবন্ধকের পরিবর্তে 32-বিট রেজিস্ট্রারগুলিতে পরিচালিত নির্দেশাবলীর মধ্যে নিবন্ধকের অংশগুলির উপর নির্ভরতাগুলি বিচ্ছিন্ন করুন। প্যাচসমূহের জন্য, এটি 32 বিট প্যাচগুলি বা MOVZX ব্যবহার করে সম্পন্ন করা যেতে পারে।

X64 এর জন্য 32 বিট অপারেডগুলির সাথে MOVZX এবং MOV সমতুল্য - তারা সমস্ত নির্ভরতা শৃঙ্খলাকে ভেঙে দেয়।

আপনার কোড দ্রুত সঞ্চালিত হয় কেন। যদি কোন নির্ভরতা না থাকে, তবে সিপিইউ অভ্যন্তরীণভাবে রেজিস্ট্রারগুলিকে পুনঃনামকরণ করতে পারে, যদিও প্রথম দর্শনে এটি দ্বিতীয় নির্দেশে প্রথম নির্দেশনা দ্বারা ব্যবহৃত নিবন্ধটি সংশোধন করে এবং উভয় সমান্তরালভাবে কার্যকর করতে পারে না। কিন্তু নিবন্ধন করার কারণে তারা করতে পারেন।

নিবন্ধন নিবন্ধনটি একটি CPU দ্বারা অভ্যন্তরীণভাবে ব্যবহৃত একটি কৌশল যা নিবন্ধকের পুনঃব্যবহার থেকে উদ্ভূত মিথ্যা তথ্য নির্ভরতাগুলি নির্বাহ করে যা ক্রমাগত নির্দেশাবলী দ্বারা তাদের মধ্যে কোনও প্রকৃত তথ্য নির্ভরতা নেই।

আমি এখন আপনি খুব সুস্পষ্ট যে দেখতে।


আপনি http://research.google.com/pubs/pub37077.html পড়তে চাইতে পারেন

টিএল; ডিআর: প্রোগ্রামগুলিতে এলোমেলোভাবে ঢোকানো নির্দেশগুলি সহজেই 5% বা তার বেশি করে কর্মক্ষমতা বাড়িয়ে তুলতে পারে, এবং না, কম্পাইলার সহজেই এটি ব্যবহার করতে পারে না। এটি সাধারণত শাখা পূর্বাভাস এবং ক্যাশে আচরণের সমন্বয়, তবে এটি ঠিক যেমন একটি রিজার্ভেশন স্টেশন স্টল (এমনকি কোনও নির্ভরতা শৃঙ্খলা নেই যা ভাঙা বা সুস্পষ্ট সংস্থান ওভার-সাবস্ক্রিপশনগুলি থাকে)।


গতি উন্নতি সবচেয়ে সম্ভবত কারণ হল যে:

  • একটি এমওভি সন্নিবেশ করা নিম্নলিখিত নির্দেশাবলী বিভিন্ন মেমরি ঠিকানা পরিবর্তন
  • যারা সরানো নির্দেশাবলী এক একটি গুরুত্বপূর্ণ শর্তাধীন শাখা ছিল
  • সেই শাখাটি শাখা পূর্বাভাস সারণিতে আলাইজিংয়ের কারণে ভুলভাবে পূর্বাভাস দেওয়া হচ্ছে
  • শাখা সরানো উদ্যান মুছে ফেলা এবং শাখা সঠিকভাবে পূর্বাভাস করা অনুমোদিত

আপনার Core2 প্রতিটি শর্তাধীন লাফ জন্য একটি পৃথক ইতিহাস রেকর্ড রাখা হয় না। পরিবর্তে এটি সমস্ত শর্তাধীন জাম্প একটি ভাগ করা ইতিহাস রাখে। বৈশ্বিক শাখার পূর্বাভাসের একটি অসুবিধা হল যে যদি শর্তসাপেক্ষ জাম্পগুলি অসম্পূর্ণ হয় তবে ইতিহাস অপ্রাসঙ্গিক তথ্য দ্বারা নিমজ্জিত হয়।

এই সামান্য শাখা ভবিষ্যদ্বাণী টিউটোরিয়াল কিভাবে শাখা ভবিষ্যদ্বাণী বাফার কাজ করে দেখায়। ক্যাশে বাফারটি শাখা নির্দেশের ঠিকানাটির নিম্ন অংশ দ্বারা সূচীকৃত। এটি ভাল কাজ করে না যতক্ষণ না দুটি গুরুত্বপূর্ণ অনিবন্ধিত শাখা একই নিচের বিট ভাগ করে। এই ক্ষেত্রে, আপনি এলিয়াসিংয়ের সাথে শেষ হয়ে যান যা অনেক ভুলপ্রাপ্ত শাখাগুলি (যা নির্দেশ পাইপলাইন স্টল করে এবং আপনার প্রোগ্রামকে ধীর করে) করে।

যদি আপনি বুঝতে চান যে কিভাবে শাখা ভুল প্রতিক্রিয়া কর্মক্ষমতা প্রভাবিত করে, এই চমৎকার উত্তরটি দেখুন: https://.com/a/11227902/1001643

কম্পাইলার সাধারণত কোন শাখাগুলি উদীয়মান এবং সেই উপনামগুলি উল্লেখযোগ্য হবে কিনা তা জানতে যথেষ্ট তথ্য নেই। তবে, তথ্য Cachegrind এবং VTune সহ সরঞ্জামগুলির সাথে রানটাইম এ নির্ধারণ করা যেতে পারে।